65#if __cplusplus >= 201103L
71namespace std _GLIBCXX_VISIBILITY(default)
73_GLIBCXX_BEGIN_NAMESPACE_VERSION
76 template<
typename _Iterator,
typename _Compare>
79 _Iterator __c, _Compare __comp)
84 std::iter_swap(__result, __b);
85 else if (__comp(__a, __c))
86 std::iter_swap(__result, __c);
88 std::iter_swap(__result, __a);
90 else if (__comp(__a, __c))
91 std::iter_swap(__result, __a);
92 else if (__comp(__b, __c))
93 std::iter_swap(__result, __c);
95 std::iter_swap(__result, __b);
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)
509 {
return __last == std::find_if_not(__first, __last, __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)
544 {
return !std::none_of(__first, __last, __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,
585 __first = std::find_if_not(__first, __last, __pred);
586 if (__first == __last)
589 return std::none_of(__first, __last, __pred);
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>)
809 __glibcxx_requires_can_increment(__first, __n);
810 __glibcxx_requires_can_increment(__result, __n);
812 return std::__copy_n(__first, __n, __result,
831 template<
typename _InputIterator,
typename _OutputIterator1,
832 typename _OutputIterator2,
typename _Predicate>
833 pair<_OutputIterator1, _OutputIterator2>
834 partition_copy(_InputIterator __first, _InputIterator __last,
835 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
839 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
840 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
841 typename iterator_traits<_InputIterator>::value_type>)
842 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
843 typename iterator_traits<_InputIterator>::value_type>)
844 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
845 typename iterator_traits<_InputIterator>::value_type>)
846 __glibcxx_requires_valid_range(__first, __last);
848 for (; __first != __last; ++__first)
849 if (__pred(*__first))
851 *__out_true = *__first;
856 *__out_false = *__first;
864 template<
typename _ForwardIterator,
typename _Predicate>
866 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
870 if (__first == __last)
872 _ForwardIterator __result = __first;
874 for (; __first != __last; ++__first)
875 if (!__pred(__first))
877 *__result = _GLIBCXX_MOVE(*__first);
900 template<
typename _ForwardIterator,
typename _Tp>
901 inline _ForwardIterator
902 remove(_ForwardIterator __first, _ForwardIterator __last,
906 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
908 __glibcxx_function_requires(_EqualOpConcept<
909 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
910 __glibcxx_requires_valid_range(__first, __last);
912 return std::__remove_if(__first, __last,
913 __gnu_cxx::__ops::__iter_equals_val(__value));
933 template<
typename _ForwardIterator,
typename _Predicate>
934 inline _ForwardIterator
935 remove_if(_ForwardIterator __first, _ForwardIterator __last,
939 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
941 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
942 typename iterator_traits<_ForwardIterator>::value_type>)
943 __glibcxx_requires_valid_range(__first, __last);
945 return std::__remove_if(__first, __last,
946 __gnu_cxx::__ops::__pred_iter(__pred));
949 template<
typename _ForwardIterator,
typename _BinaryPredicate>
951 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
952 _BinaryPredicate __binary_pred)
954 if (__first == __last)
956 _ForwardIterator __next = __first;
957 while (++__next != __last)
959 if (__binary_pred(__first, __next))
966 template<
typename _ForwardIterator,
typename _BinaryPredicate>
968 __unique(_ForwardIterator __first, _ForwardIterator __last,
969 _BinaryPredicate __binary_pred)
972 __first = std::__adjacent_find(__first, __last, __binary_pred);
973 if (__first == __last)
977 _ForwardIterator __dest = __first;
979 while (++__first != __last)
980 if (!__binary_pred(__dest, __first))
981 *++__dest = _GLIBCXX_MOVE(*__first);
999 template<
typename _ForwardIterator>
1000 inline _ForwardIterator
1001 unique(_ForwardIterator __first, _ForwardIterator __last)
1004 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1006 __glibcxx_function_requires(_EqualityComparableConcept<
1007 typename iterator_traits<_ForwardIterator>::value_type>)
1008 __glibcxx_requires_valid_range(__first, __last);
1010 return std::__unique(__first, __last,
1011 __gnu_cxx::__ops::__iter_equal_to_iter());
1029 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1030 inline _ForwardIterator
1031 unique(_ForwardIterator __first, _ForwardIterator __last,
1032 _BinaryPredicate __binary_pred)
1035 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1037 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1038 typename iterator_traits<_ForwardIterator>::value_type,
1039 typename iterator_traits<_ForwardIterator>::value_type>)
1040 __glibcxx_requires_valid_range(__first, __last);
1042 return std::__unique(__first, __last,
1043 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1052 template<
typename _ForwardIterator,
typename _OutputIterator,
1053 typename _BinaryPredicate>
1056 _OutputIterator __result, _BinaryPredicate __binary_pred,
1060 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1061 typename iterator_traits<_ForwardIterator>::value_type,
1062 typename iterator_traits<_ForwardIterator>::value_type>)
1064 _ForwardIterator __next = __first;
1065 *__result = *__first;
1066 while (++__next != __last)
1067 if (!__binary_pred(__first, __next))
1070 *++__result = *__first;
1081 template<
typename _InputIterator,
typename _OutputIterator,
1082 typename _BinaryPredicate>
1085 _OutputIterator __result, _BinaryPredicate __binary_pred,
1089 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1090 typename iterator_traits<_InputIterator>::value_type,
1091 typename iterator_traits<_InputIterator>::value_type>)
1093 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1094 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1096 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1097 *__result = __value;
1098 while (++__first != __last)
1099 if (!__rebound_pred(__first, __value))
1102 *++__result = __value;
1113 template<
typename _InputIterator,
typename _ForwardIterator,
1114 typename _BinaryPredicate>
1117 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1121 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1122 typename iterator_traits<_ForwardIterator>::value_type,
1123 typename iterator_traits<_InputIterator>::value_type>)
1124 *__result = *__first;
1125 while (++__first != __last)
1126 if (!__binary_pred(__result, __first))
1127 *++__result = *__first;
1136 template<
typename _B
idirectionalIterator>
1138 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1142 if (__first == __last || __first == --__last)
1146 std::iter_swap(__first, __last);
1156 template<
typename _RandomAccessIterator>
1158 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1161 if (__first == __last)
1164 while (__first < __last)
1166 std::iter_swap(__first, __last);
1184 template<
typename _B
idirectionalIterator>
1186 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1189 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1190 _BidirectionalIterator>)
1191 __glibcxx_requires_valid_range(__first, __last);
1211 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1213 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1214 _OutputIterator __result)
1217 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1218 _BidirectionalIterator>)
1219 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1220 typename iterator_traits<_BidirectionalIterator>::value_type>)
1221 __glibcxx_requires_valid_range(__first, __last);
1223 while (__first != __last)
1226 *__result = *__last;
1236 template<
typename _Eucl
ideanRingElement>
1237 _EuclideanRingElement
1238 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1242 _EuclideanRingElement __t = __m % __n;
1249 inline namespace _V2
1253 template<
typename _ForwardIterator>
1256 _ForwardIterator __middle,
1257 _ForwardIterator __last,
1260 if (__first == __middle)
1262 else if (__last == __middle)
1265 _ForwardIterator __first2 = __middle;
1268 std::iter_swap(__first, __first2);
1271 if (__first == __middle)
1272 __middle = __first2;
1274 while (__first2 != __last);
1276 _ForwardIterator __ret = __first;
1278 __first2 = __middle;
1280 while (__first2 != __last)
1282 std::iter_swap(__first, __first2);
1285 if (__first == __middle)
1286 __middle = __first2;
1287 else if (__first2 == __last)
1288 __first2 = __middle;
1294 template<
typename _B
idirectionalIterator>
1295 _BidirectionalIterator
1297 _BidirectionalIterator __middle,
1298 _BidirectionalIterator __last,
1302 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1303 _BidirectionalIterator>)
1305 if (__first == __middle)
1307 else if (__last == __middle)
1313 while (__first != __middle && __middle != __last)
1315 std::iter_swap(__first, --__last);
1319 if (__first == __middle)
1332 template<
typename _RandomAccessIterator>
1333 _RandomAccessIterator
1335 _RandomAccessIterator __middle,
1336 _RandomAccessIterator __last,
1340 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1341 _RandomAccessIterator>)
1343 if (__first == __middle)
1345 else if (__last == __middle)
1348 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1350 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1353 _Distance __n = __last - __first;
1354 _Distance __k = __middle - __first;
1356 if (__k == __n - __k)
1358 std::swap_ranges(__first, __middle, __middle);
1362 _RandomAccessIterator __p = __first;
1363 _RandomAccessIterator __ret = __first + (__last - __middle);
1367 if (__k < __n - __k)
1369 if (__is_pod(_ValueType) && __k == 1)
1371 _ValueType __t = _GLIBCXX_MOVE(*__p);
1372 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1373 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1376 _RandomAccessIterator __q = __p + __k;
1377 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1379 std::iter_swap(__p, __q);
1386 std::swap(__n, __k);
1392 if (__is_pod(_ValueType) && __k == 1)
1394 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1395 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1396 *__p = _GLIBCXX_MOVE(__t);
1399 _RandomAccessIterator __q = __p + __n;
1401 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1405 std::iter_swap(__p, __q);
1410 std::swap(__n, __k);
1438 template<
typename _ForwardIterator>
1439 inline _ForwardIterator
1440 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1441 _ForwardIterator __last)
1444 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1446 __glibcxx_requires_valid_range(__first, __middle);
1447 __glibcxx_requires_valid_range(__middle, __last);
1475 template<
typename _ForwardIterator,
typename _OutputIterator>
1476 inline _OutputIterator
1477 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1478 _ForwardIterator __last, _OutputIterator __result)
1481 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1482 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1483 typename iterator_traits<_ForwardIterator>::value_type>)
1484 __glibcxx_requires_valid_range(__first, __middle);
1485 __glibcxx_requires_valid_range(__middle, __last);
1487 return std::copy(__first, __middle,
1488 std::copy(__middle, __last, __result));
1492 template<
typename _ForwardIterator,
typename _Predicate>
1497 if (__first == __last)
1500 while (__pred(*__first))
1501 if (++__first == __last)
1504 _ForwardIterator __next = __first;
1506 while (++__next != __last)
1507 if (__pred(*__next))
1509 std::iter_swap(__first, __next);
1517 template<
typename _B
idirectionalIterator,
typename _Predicate>
1518 _BidirectionalIterator
1519 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1525 if (__first == __last)
1527 else if (__pred(*__first))
1533 if (__first == __last)
1535 else if (!
bool(__pred(*__last)))
1539 std::iter_swap(__first, __last);
1552 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1556 _ForwardIterator __last,
1557 _Predicate __pred, _Distance __len,
1559 _Distance __buffer_size)
1564 if (__len <= __buffer_size)
1566 _ForwardIterator __result1 = __first;
1567 _Pointer __result2 = __buffer;
1572 *__result2 = _GLIBCXX_MOVE(*__first);
1575 for (; __first != __last; ++__first)
1576 if (__pred(__first))
1578 *__result1 = _GLIBCXX_MOVE(*__first);
1583 *__result2 = _GLIBCXX_MOVE(*__first);
1587 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1591 _ForwardIterator __middle = __first;
1593 _ForwardIterator __left_split =
1595 __len / 2, __buffer,
1600 _Distance __right_len = __len - __len / 2;
1601 _ForwardIterator __right_split =
1608 __buffer, __buffer_size);
1610 return std::rotate(__left_split, __middle, __right_split);
1613 template<
typename _ForwardIterator,
typename _Predicate>
1615 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1620 if (__first == __last)
1623 typedef typename iterator_traits<_ForwardIterator>::value_type
1625 typedef typename iterator_traits<_ForwardIterator>::difference_type
1628 _Temporary_buffer<_ForwardIterator, _ValueType>
1632 _DistanceType(__buf.requested_size()),
1634 _DistanceType(__buf.size()));
1654 template<
typename _ForwardIterator,
typename _Predicate>
1655 inline _ForwardIterator
1656 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1660 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1662 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1663 typename iterator_traits<_ForwardIterator>::value_type>)
1664 __glibcxx_requires_valid_range(__first, __last);
1666 return std::__stable_partition(__first, __last,
1667 __gnu_cxx::__ops::__pred_iter(__pred));
1671 template<
typename _RandomAccessIterator,
typename _Compare>
1674 _RandomAccessIterator __middle,
1675 _RandomAccessIterator __last, _Compare __comp)
1677 std::__make_heap(__first, __middle, __comp);
1678 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1679 if (__comp(__i, __first))
1680 std::__pop_heap(__first, __middle, __i, __comp);
1685 template<
typename _InputIterator,
typename _RandomAccessIterator,
1687 _RandomAccessIterator
1688 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1689 _RandomAccessIterator __result_first,
1690 _RandomAccessIterator __result_last,
1693 typedef typename iterator_traits<_InputIterator>::value_type
1695 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1696 typedef typename _RItTraits::difference_type _DistanceType;
1698 if (__result_first == __result_last)
1699 return __result_last;
1700 _RandomAccessIterator __result_real_last = __result_first;
1701 while (__first != __last && __result_real_last != __result_last)
1703 *__result_real_last = *__first;
1704 ++__result_real_last;
1708 std::__make_heap(__result_first, __result_real_last, __comp);
1709 while (__first != __last)
1711 if (__comp(__first, __result_first))
1712 std::__adjust_heap(__result_first, _DistanceType(0),
1713 _DistanceType(__result_real_last
1715 _InputValueType(*__first), __comp);
1718 std::__sort_heap(__result_first, __result_real_last, __comp);
1719 return __result_real_last;
1740 template<
typename _InputIterator,
typename _RandomAccessIterator>
1741 inline _RandomAccessIterator
1742 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1743 _RandomAccessIterator __result_first,
1744 _RandomAccessIterator __result_last)
1746#ifdef _GLIBCXX_CONCEPT_CHECKS
1747 typedef typename iterator_traits<_InputIterator>::value_type
1749 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1754 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1755 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1757 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1759 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1760 __glibcxx_requires_valid_range(__first, __last);
1761 __glibcxx_requires_irreflexive(__first, __last);
1762 __glibcxx_requires_valid_range(__result_first, __result_last);
1764 return std::__partial_sort_copy(__first, __last,
1765 __result_first, __result_last,
1766 __gnu_cxx::__ops::__iter_less_iter());
1789 template<
typename _InputIterator,
typename _RandomAccessIterator,
1791 inline _RandomAccessIterator
1792 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1793 _RandomAccessIterator __result_first,
1794 _RandomAccessIterator __result_last,
1797#ifdef _GLIBCXX_CONCEPT_CHECKS
1798 typedef typename iterator_traits<_InputIterator>::value_type
1800 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1805 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1806 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1807 _RandomAccessIterator>)
1808 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1810 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1811 _InputValueType, _OutputValueType>)
1812 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1813 _OutputValueType, _OutputValueType>)
1814 __glibcxx_requires_valid_range(__first, __last);
1815 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1816 __glibcxx_requires_valid_range(__result_first, __result_last);
1818 return std::__partial_sort_copy(__first, __last,
1819 __result_first, __result_last,
1820 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1824 template<
typename _RandomAccessIterator,
typename _Compare>
1829 typename iterator_traits<_RandomAccessIterator>::value_type
1830 __val = _GLIBCXX_MOVE(*__last);
1831 _RandomAccessIterator __next = __last;
1833 while (__comp(__val, __next))
1835 *__last = _GLIBCXX_MOVE(*__next);
1839 *__last = _GLIBCXX_MOVE(__val);
1843 template<
typename _RandomAccessIterator,
typename _Compare>
1846 _RandomAccessIterator __last, _Compare __comp)
1848 if (__first == __last)
return;
1850 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1852 if (__comp(__i, __first))
1854 typename iterator_traits<_RandomAccessIterator>::value_type
1855 __val = _GLIBCXX_MOVE(*__i);
1856 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1857 *__first = _GLIBCXX_MOVE(__val);
1861 __gnu_cxx::__ops::__val_comp_iter(__comp));
1866 template<
typename _RandomAccessIterator,
typename _Compare>
1869 _RandomAccessIterator __last, _Compare __comp)
1871 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1873 __gnu_cxx::__ops::__val_comp_iter(__comp));
1880 enum { _S_threshold = 16 };
1883 template<
typename _RandomAccessIterator,
typename _Compare>
1886 _RandomAccessIterator __last, _Compare __comp)
1888 if (__last - __first >
int(_S_threshold))
1899 template<
typename _RandomAccessIterator,
typename _Compare>
1900 _RandomAccessIterator
1902 _RandomAccessIterator __last,
1903 _RandomAccessIterator __pivot, _Compare __comp)
1907 while (__comp(__first, __pivot))
1910 while (__comp(__pivot, __last))
1912 if (!(__first < __last))
1914 std::iter_swap(__first, __last);
1920 template<
typename _RandomAccessIterator,
typename _Compare>
1921 inline _RandomAccessIterator
1923 _RandomAccessIterator __last, _Compare __comp)
1925 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1931 template<
typename _RandomAccessIterator,
typename _Compare>
1933 __partial_sort(_RandomAccessIterator __first,
1934 _RandomAccessIterator __middle,
1935 _RandomAccessIterator __last,
1939 std::__sort_heap(__first, __middle, __comp);
1943 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1946 _RandomAccessIterator __last,
1947 _Size __depth_limit, _Compare __comp)
1949 while (__last - __first >
int(_S_threshold))
1951 if (__depth_limit == 0)
1953 std::__partial_sort(__first, __last, __last, __comp);
1957 _RandomAccessIterator __cut =
1966 template<
typename _RandomAccessIterator,
typename _Compare>
1968 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1971 if (__first != __last)
1980 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1982 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1983 _RandomAccessIterator __last, _Size __depth_limit,
1986 while (__last - __first > 3)
1988 if (__depth_limit == 0)
1992 std::iter_swap(__first, __nth);
1996 _RandomAccessIterator __cut =
2026 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2027 inline _ForwardIterator
2028 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2029 const _Tp& __val, _Compare __comp)
2032 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2033 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2034 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2035 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2038 return std::__lower_bound(__first, __last, __val,
2039 __gnu_cxx::__ops::__iter_comp_val(__comp));
2042 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2044 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2045 const _Tp& __val, _Compare __comp)
2047 typedef typename iterator_traits<_ForwardIterator>::difference_type
2054 _DistanceType __half = __len >> 1;
2055 _ForwardIterator __middle = __first;
2057 if (__comp(__val, __middle))
2063 __len = __len - __half - 1;
2080 template<
typename _ForwardIterator,
typename _Tp>
2081 inline _ForwardIterator
2082 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2086 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2087 __glibcxx_function_requires(_LessThanOpConcept<
2088 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2089 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2091 return std::__upper_bound(__first, __last, __val,
2092 __gnu_cxx::__ops::__val_less_iter());
2110 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2111 inline _ForwardIterator
2112 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2113 const _Tp& __val, _Compare __comp)
2116 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2117 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2118 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2119 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2122 return std::__upper_bound(__first, __last, __val,
2123 __gnu_cxx::__ops::__val_comp_iter(__comp));
2126 template<
typename _ForwardIterator,
typename _Tp,
2127 typename _CompareItTp,
typename _CompareTpIt>
2128 pair<_ForwardIterator, _ForwardIterator>
2129 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2131 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2133 typedef typename iterator_traits<_ForwardIterator>::difference_type
2140 _DistanceType __half = __len >> 1;
2141 _ForwardIterator __middle = __first;
2143 if (__comp_it_val(__middle, __val))
2147 __len = __len - __half - 1;
2149 else if (__comp_val_it(__val, __middle))
2153 _ForwardIterator __left
2154 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2156 _ForwardIterator __right
2157 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2158 return pair<_ForwardIterator, _ForwardIterator>(__left, __right);
2161 return pair<_ForwardIterator, _ForwardIterator>(__first, __first);
2181 template<
typename _ForwardIterator,
typename _Tp>
2182 inline pair<_ForwardIterator, _ForwardIterator>
2183 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2187 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2188 __glibcxx_function_requires(_LessThanOpConcept<
2189 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2190 __glibcxx_function_requires(_LessThanOpConcept<
2191 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2192 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2193 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2195 return std::__equal_range(__first, __last, __val,
2196 __gnu_cxx::__ops::__iter_less_val(),
2197 __gnu_cxx::__ops::__val_less_iter());
2217 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2218 inline pair<_ForwardIterator, _ForwardIterator>
2219 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2220 const _Tp& __val, _Compare __comp)
2223 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2224 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2225 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2226 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2227 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2228 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2230 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2233 return std::__equal_range(__first, __last, __val,
2234 __gnu_cxx::__ops::__iter_comp_val(__comp),
2235 __gnu_cxx::__ops::__val_comp_iter(__comp));
2250 template<
typename _ForwardIterator,
typename _Tp>
2252 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2256 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2257 __glibcxx_function_requires(_LessThanOpConcept<
2258 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2259 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2260 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2262 _ForwardIterator __i
2263 = std::__lower_bound(__first, __last, __val,
2264 __gnu_cxx::__ops::__iter_less_val());
2265 return __i != __last && !(__val < *__i);
2283 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2285 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2286 const _Tp& __val, _Compare __comp)
2289 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2290 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2291 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2292 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2294 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2297 _ForwardIterator __i
2298 = std::__lower_bound(__first, __last, __val,
2299 __gnu_cxx::__ops::__iter_comp_val(__comp));
2300 return __i != __last && !bool(__comp(__val, *__i));
2306 template<
typename _InputIterator1,
typename _InputIterator2,
2307 typename _OutputIterator,
typename _Compare>
2310 _InputIterator2 __first2, _InputIterator2 __last2,
2311 _OutputIterator __result, _Compare __comp)
2313 while (__first1 != __last1 && __first2 != __last2)
2315 if (__comp(__first2, __first1))
2317 *__result = _GLIBCXX_MOVE(*__first2);
2322 *__result = _GLIBCXX_MOVE(*__first1);
2327 if (__first1 != __last1)
2328 _GLIBCXX_MOVE3(__first1, __last1, __result);
2332 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2333 typename _BidirectionalIterator3,
typename _Compare>
2336 _BidirectionalIterator1 __last1,
2337 _BidirectionalIterator2 __first2,
2338 _BidirectionalIterator2 __last2,
2339 _BidirectionalIterator3 __result,
2342 if (__first1 == __last1)
2344 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2347 else if (__first2 == __last2)
2354 if (__comp(__last2, __last1))
2356 *--__result = _GLIBCXX_MOVE(*__last1);
2357 if (__first1 == __last1)
2359 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2366 *--__result = _GLIBCXX_MOVE(*__last2);
2367 if (__first2 == __last2)
2375 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2377 _BidirectionalIterator1
2379 _BidirectionalIterator1 __middle,
2380 _BidirectionalIterator1 __last,
2381 _Distance __len1, _Distance __len2,
2382 _BidirectionalIterator2 __buffer,
2383 _Distance __buffer_size)
2385 _BidirectionalIterator2 __buffer_end;
2386 if (__len1 > __len2 && __len2 <= __buffer_size)
2390 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2391 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2392 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2397 else if (__len1 <= __buffer_size)
2401 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2402 _GLIBCXX_MOVE3(__middle, __last, __first);
2403 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2409 return std::rotate(__first, __middle, __last);
2413 template<
typename _BidirectionalIterator,
typename _Distance,
2414 typename _Pointer,
typename _Compare>
2417 _BidirectionalIterator __middle,
2418 _BidirectionalIterator __last,
2419 _Distance __len1, _Distance __len2,
2420 _Pointer __buffer, _Distance __buffer_size,
2423 if (__len1 <= __len2 && __len1 <= __buffer_size)
2425 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2429 else if (__len2 <= __buffer_size)
2431 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2433 __buffer_end, __last, __comp);
2437 _BidirectionalIterator __first_cut = __first;
2438 _BidirectionalIterator __second_cut = __middle;
2439 _Distance __len11 = 0;
2440 _Distance __len22 = 0;
2441 if (__len1 > __len2)
2443 __len11 = __len1 / 2;
2446 = std::__lower_bound(__middle, __last, *__first_cut,
2447 __gnu_cxx::__ops::__iter_comp_val(__comp));
2452 __len22 = __len2 / 2;
2455 = std::__upper_bound(__first, __middle, *__second_cut,
2456 __gnu_cxx::__ops::__val_comp_iter(__comp));
2460 _BidirectionalIterator __new_middle
2462 __len1 - __len11, __len22, __buffer,
2465 __len22, __buffer, __buffer_size, __comp);
2468 __len2 - __len22, __buffer,
2469 __buffer_size, __comp);
2474 template<
typename _BidirectionalIterator,
typename _Distance,
2478 _BidirectionalIterator __middle,
2479 _BidirectionalIterator __last,
2480 _Distance __len1, _Distance __len2,
2483 if (__len1 == 0 || __len2 == 0)
2486 if (__len1 + __len2 == 2)
2488 if (__comp(__middle, __first))
2489 std::iter_swap(__first, __middle);
2493 _BidirectionalIterator __first_cut = __first;
2494 _BidirectionalIterator __second_cut = __middle;
2495 _Distance __len11 = 0;
2496 _Distance __len22 = 0;
2497 if (__len1 > __len2)
2499 __len11 = __len1 / 2;
2502 = std::__lower_bound(__middle, __last, *__first_cut,
2503 __gnu_cxx::__ops::__iter_comp_val(__comp));
2508 __len22 = __len2 / 2;
2511 = std::__upper_bound(__first, __middle, *__second_cut,
2512 __gnu_cxx::__ops::__val_comp_iter(__comp));
2516 _BidirectionalIterator __new_middle
2517 = std::rotate(__first_cut, __middle, __second_cut);
2519 __len11, __len22, __comp);
2521 __len1 - __len11, __len2 - __len22, __comp);
2524 template<
typename _B
idirectionalIterator,
typename _Compare>
2526 __inplace_merge(_BidirectionalIterator __first,
2527 _BidirectionalIterator __middle,
2528 _BidirectionalIterator __last,
2531 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2533 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2536 if (__first == __middle || __middle == __last)
2539 const _DistanceType __len1 =
std::distance(__first, __middle);
2540 const _DistanceType __len2 =
std::distance(__middle, __last);
2542 typedef _Temporary_buffer<_BidirectionalIterator, _ValueType> _TmpBuf;
2543 _TmpBuf __buf(__first, __len1 + __len2);
2545 if (__buf.begin() == 0)
2547 (__first, __middle, __last, __len1, __len2, __comp);
2550 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2551 _DistanceType(__buf.size()), __comp);
2572 template<
typename _B
idirectionalIterator>
2574 inplace_merge(_BidirectionalIterator __first,
2575 _BidirectionalIterator __middle,
2576 _BidirectionalIterator __last)
2579 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2580 _BidirectionalIterator>)
2581 __glibcxx_function_requires(_LessThanComparableConcept<
2582 typename iterator_traits<_BidirectionalIterator>::value_type>)
2583 __glibcxx_requires_sorted(__first, __middle);
2584 __glibcxx_requires_sorted(__middle, __last);
2585 __glibcxx_requires_irreflexive(__first, __last);
2587 std::__inplace_merge(__first, __middle, __last,
2588 __gnu_cxx::__ops::__iter_less_iter());
2613 template<
typename _B
idirectionalIterator,
typename _Compare>
2615 inplace_merge(_BidirectionalIterator __first,
2616 _BidirectionalIterator __middle,
2617 _BidirectionalIterator __last,
2621 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2622 _BidirectionalIterator>)
2623 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2624 typename iterator_traits<_BidirectionalIterator>::value_type,
2625 typename iterator_traits<_BidirectionalIterator>::value_type>)
2626 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2627 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2628 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2630 std::__inplace_merge(__first, __middle, __last,
2631 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2636 template<
typename _InputIterator,
typename _OutputIterator,
2640 _InputIterator __first2, _InputIterator __last2,
2641 _OutputIterator __result, _Compare __comp)
2643 while (__first1 != __last1 && __first2 != __last2)
2645 if (__comp(__first2, __first1))
2647 *__result = _GLIBCXX_MOVE(*__first2);
2652 *__result = _GLIBCXX_MOVE(*__first1);
2657 return _GLIBCXX_MOVE3(__first2, __last2,
2658 _GLIBCXX_MOVE3(__first1, __last1,
2662 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2663 typename _Distance,
typename _Compare>
2665 __merge_sort_loop(_RandomAccessIterator1 __first,
2666 _RandomAccessIterator1 __last,
2667 _RandomAccessIterator2 __result, _Distance __step_size,
2670 const _Distance __two_step = 2 * __step_size;
2672 while (__last - __first >= __two_step)
2675 __first + __step_size,
2676 __first + __two_step,
2678 __first += __two_step;
2680 __step_size =
std::min(_Distance(__last - __first), __step_size);
2683 __first + __step_size, __last, __result, __comp);
2686 template<
typename _RandomAccessIterator,
typename _Distance,
2689 __chunk_insertion_sort(_RandomAccessIterator __first,
2690 _RandomAccessIterator __last,
2691 _Distance __chunk_size, _Compare __comp)
2693 while (__last - __first >= __chunk_size)
2696 __first += __chunk_size;
2701 enum { _S_chunk_size = 7 };
2703 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2705 __merge_sort_with_buffer(_RandomAccessIterator __first,
2706 _RandomAccessIterator __last,
2707 _Pointer __buffer, _Compare __comp)
2709 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2712 const _Distance __len = __last - __first;
2713 const _Pointer __buffer_last = __buffer + __len;
2715 _Distance __step_size = _S_chunk_size;
2716 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2718 while (__step_size < __len)
2720 std::__merge_sort_loop(__first, __last, __buffer,
2721 __step_size, __comp);
2723 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2724 __step_size, __comp);
2729 template<
typename _RandomAccessIterator,
typename _Pointer,
2730 typename _Distance,
typename _Compare>
2732 __stable_sort_adaptive(_RandomAccessIterator __first,
2733 _RandomAccessIterator __last,
2734 _Pointer __buffer, _Distance __buffer_size,
2737 const _Distance __len = (__last - __first + 1) / 2;
2738 const _RandomAccessIterator __middle = __first + __len;
2739 if (__len > __buffer_size)
2741 std::__stable_sort_adaptive(__first, __middle, __buffer,
2742 __buffer_size, __comp);
2743 std::__stable_sort_adaptive(__middle, __last, __buffer,
2744 __buffer_size, __comp);
2748 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2749 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2752 _Distance(__middle - __first),
2753 _Distance(__last - __middle),
2754 __buffer, __buffer_size,
2759 template<
typename _RandomAccessIterator,
typename _Compare>
2762 _RandomAccessIterator __last, _Compare __comp)
2764 if (__last - __first < 15)
2769 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2785 template<
typename _InputIterator1,
typename _InputIterator2,
2788 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2789 _InputIterator2 __first2, _InputIterator2 __last2,
2792 while (__first1 != __last1 && __first2 != __last2)
2793 if (__comp(__first2, __first1))
2795 else if (__comp(__first1, __first2))
2803 return __first2 == __last2;
2824 template<
typename _InputIterator1,
typename _InputIterator2>
2826 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2827 _InputIterator2 __first2, _InputIterator2 __last2)
2830 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2831 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2832 __glibcxx_function_requires(_LessThanOpConcept<
2833 typename iterator_traits<_InputIterator1>::value_type,
2834 typename iterator_traits<_InputIterator2>::value_type>)
2835 __glibcxx_function_requires(_LessThanOpConcept<
2836 typename iterator_traits<_InputIterator2>::value_type,
2837 typename iterator_traits<_InputIterator1>::value_type>)
2838 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2839 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2840 __glibcxx_requires_irreflexive2(__first1, __last1);
2841 __glibcxx_requires_irreflexive2(__first2, __last2);
2843 return std::__includes(__first1, __last1, __first2, __last2,
2844 __gnu_cxx::__ops::__iter_less_iter());
2868 template<
typename _InputIterator1,
typename _InputIterator2,
2871 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2872 _InputIterator2 __first2, _InputIterator2 __last2,
2876 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2877 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2878 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2879 typename iterator_traits<_InputIterator1>::value_type,
2880 typename iterator_traits<_InputIterator2>::value_type>)
2881 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2882 typename iterator_traits<_InputIterator2>::value_type,
2883 typename iterator_traits<_InputIterator1>::value_type>)
2884 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2885 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2886 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2887 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2889 return std::__includes(__first1, __last1, __first2, __last2,
2890 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2903 template<
typename _B
idirectionalIterator,
typename _Compare>
2905 __next_permutation(_BidirectionalIterator __first,
2906 _BidirectionalIterator __last, _Compare __comp)
2908 if (__first == __last)
2910 _BidirectionalIterator __i = __first;
2919 _BidirectionalIterator __ii = __i;
2921 if (__comp(__i, __ii))
2923 _BidirectionalIterator __j = __last;
2924 while (!__comp(__i, --__j))
2926 std::iter_swap(__i, __j);
2952 template<
typename _B
idirectionalIterator>
2954 next_permutation(_BidirectionalIterator __first,
2955 _BidirectionalIterator __last)
2958 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2959 _BidirectionalIterator>)
2960 __glibcxx_function_requires(_LessThanComparableConcept<
2961 typename iterator_traits<_BidirectionalIterator>::value_type>)
2962 __glibcxx_requires_valid_range(__first, __last);
2963 __glibcxx_requires_irreflexive(__first, __last);
2965 return std::__next_permutation
2966 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2984 template<
typename _B
idirectionalIterator,
typename _Compare>
2986 next_permutation(_BidirectionalIterator __first,
2987 _BidirectionalIterator __last, _Compare __comp)
2990 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2991 _BidirectionalIterator>)
2992 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2993 typename iterator_traits<_BidirectionalIterator>::value_type,
2994 typename iterator_traits<_BidirectionalIterator>::value_type>)
2995 __glibcxx_requires_valid_range(__first, __last);
2996 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2998 return std::__next_permutation
2999 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3002 template<
typename _B
idirectionalIterator,
typename _Compare>
3004 __prev_permutation(_BidirectionalIterator __first,
3005 _BidirectionalIterator __last, _Compare __comp)
3007 if (__first == __last)
3009 _BidirectionalIterator __i = __first;
3018 _BidirectionalIterator __ii = __i;
3020 if (__comp(__ii, __i))
3022 _BidirectionalIterator __j = __last;
3023 while (!__comp(--__j, __i))
3025 std::iter_swap(__i, __j);
3052 template<
typename _B
idirectionalIterator>
3054 prev_permutation(_BidirectionalIterator __first,
3055 _BidirectionalIterator __last)
3058 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3059 _BidirectionalIterator>)
3060 __glibcxx_function_requires(_LessThanComparableConcept<
3061 typename iterator_traits<_BidirectionalIterator>::value_type>)
3062 __glibcxx_requires_valid_range(__first, __last);
3063 __glibcxx_requires_irreflexive(__first, __last);
3065 return std::__prev_permutation(__first, __last,
3066 __gnu_cxx::__ops::__iter_less_iter());
3084 template<
typename _B
idirectionalIterator,
typename _Compare>
3086 prev_permutation(_BidirectionalIterator __first,
3087 _BidirectionalIterator __last, _Compare __comp)
3090 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3091 _BidirectionalIterator>)
3092 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3093 typename iterator_traits<_BidirectionalIterator>::value_type,
3094 typename iterator_traits<_BidirectionalIterator>::value_type>)
3095 __glibcxx_requires_valid_range(__first, __last);
3096 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3098 return std::__prev_permutation(__first, __last,
3099 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3105 template<
typename _InputIterator,
typename _OutputIterator,
3106 typename _Predicate,
typename _Tp>
3108 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3109 _OutputIterator __result,
3110 _Predicate __pred,
const _Tp& __new_value)
3112 for (; __first != __last; ++__first, (void)++__result)
3113 if (__pred(__first))
3114 *__result = __new_value;
3116 *__result = *__first;
3134 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3135 inline _OutputIterator
3136 replace_copy(_InputIterator __first, _InputIterator __last,
3137 _OutputIterator __result,
3138 const _Tp& __old_value,
const _Tp& __new_value)
3141 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3142 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3143 typename iterator_traits<_InputIterator>::value_type>)
3144 __glibcxx_function_requires(_EqualOpConcept<
3145 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3146 __glibcxx_requires_valid_range(__first, __last);
3148 return std::__replace_copy_if(__first, __last, __result,
3149 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3168 template<
typename _InputIterator,
typename _OutputIterator,
3169 typename _Predicate,
typename _Tp>
3170 inline _OutputIterator
3171 replace_copy_if(_InputIterator __first, _InputIterator __last,
3172 _OutputIterator __result,
3173 _Predicate __pred,
const _Tp& __new_value)
3176 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3177 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3178 typename iterator_traits<_InputIterator>::value_type>)
3179 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3180 typename iterator_traits<_InputIterator>::value_type>)
3181 __glibcxx_requires_valid_range(__first, __last);
3183 return std::__replace_copy_if(__first, __last, __result,
3184 __gnu_cxx::__ops::__pred_iter(__pred),
3188 template<
typename _InputIterator,
typename _Predicate>
3189 typename iterator_traits<_InputIterator>::difference_type
3190 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3192 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3193 for (; __first != __last; ++__first)
3194 if (__pred(__first))
3199#if __cplusplus >= 201103L
3207 template<
typename _ForwardIterator>
3209 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3210 {
return std::is_sorted_until(__first, __last) == __last; }
3221 template<
typename _ForwardIterator,
typename _Compare>
3223 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3225 {
return std::is_sorted_until(__first, __last, __comp) == __last; }
3227 template<
typename _ForwardIterator,
typename _Compare>
3229 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3232 if (__first == __last)
3235 _ForwardIterator __next = __first;
3236 for (++__next; __next != __last; __first = __next, (void)++__next)
3237 if (__comp(__next, __first))
3250 template<
typename _ForwardIterator>
3251 inline _ForwardIterator
3252 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3255 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3256 __glibcxx_function_requires(_LessThanComparableConcept<
3257 typename iterator_traits<_ForwardIterator>::value_type>)
3258 __glibcxx_requires_valid_range(__first, __last);
3259 __glibcxx_requires_irreflexive(__first, __last);
3261 return std::__is_sorted_until(__first, __last,
3262 __gnu_cxx::__ops::__iter_less_iter());
3274 template<
typename _ForwardIterator,
typename _Compare>
3275 inline _ForwardIterator
3276 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3280 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3281 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3282 typename iterator_traits<_ForwardIterator>::value_type,
3283 typename iterator_traits<_ForwardIterator>::value_type>)
3284 __glibcxx_requires_valid_range(__first, __last);
3285 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3287 return std::__is_sorted_until(__first, __last,
3288 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3299 template<
typename _Tp>
3300 _GLIBCXX14_CONSTEXPR
3301 inline pair<const _Tp&, const _Tp&>
3305 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3307 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3320 template<
typename _Tp,
typename _Compare>
3321 _GLIBCXX14_CONSTEXPR
3322 inline pair<const _Tp&, const _Tp&>
3323 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3329 template<
typename _ForwardIterator,
typename _Compare>
3330 _GLIBCXX14_CONSTEXPR
3331 pair<_ForwardIterator, _ForwardIterator>
3332 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3335 _ForwardIterator __next = __first;
3336 if (__first == __last
3337 || ++__next == __last)
3340 _ForwardIterator __min{}, __max{};
3341 if (__comp(__next, __first))
3355 while (__first != __last)
3358 if (++__next == __last)
3360 if (__comp(__first, __min))
3362 else if (!__comp(__first, __max))
3367 if (__comp(__next, __first))
3369 if (__comp(__next, __min))
3371 if (!__comp(__first, __max))
3376 if (__comp(__first, __min))
3378 if (!__comp(__next, __max))
3400 template<
typename _ForwardIterator>
3401 _GLIBCXX14_CONSTEXPR
3402 inline pair<_ForwardIterator, _ForwardIterator>
3403 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3406 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3407 __glibcxx_function_requires(_LessThanComparableConcept<
3408 typename iterator_traits<_ForwardIterator>::value_type>)
3409 __glibcxx_requires_valid_range(__first, __last);
3410 __glibcxx_requires_irreflexive(__first, __last);
3412 return std::__minmax_element(__first, __last,
3413 __gnu_cxx::__ops::__iter_less_iter());
3428 template<
typename _ForwardIterator,
typename _Compare>
3429 _GLIBCXX14_CONSTEXPR
3430 inline pair<_ForwardIterator, _ForwardIterator>
3431 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3435 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3436 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3437 typename iterator_traits<_ForwardIterator>::value_type,
3438 typename iterator_traits<_ForwardIterator>::value_type>)
3439 __glibcxx_requires_valid_range(__first, __last);
3440 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3442 return std::__minmax_element(__first, __last,
3443 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3447 template<
typename _Tp>
3448 _GLIBCXX14_CONSTEXPR
3450 min(initializer_list<_Tp> __l)
3451 {
return *std::min_element(__l.begin(), __l.end()); }
3453 template<
typename _Tp,
typename _Compare>
3454 _GLIBCXX14_CONSTEXPR
3456 min(initializer_list<_Tp> __l, _Compare __comp)
3457 {
return *std::min_element(__l.begin(), __l.end(), __comp); }
3459 template<
typename _Tp>
3460 _GLIBCXX14_CONSTEXPR
3462 max(initializer_list<_Tp> __l)
3463 {
return *std::max_element(__l.begin(), __l.end()); }
3465 template<
typename _Tp,
typename _Compare>
3466 _GLIBCXX14_CONSTEXPR
3468 max(initializer_list<_Tp> __l, _Compare __comp)
3469 {
return *std::max_element(__l.begin(), __l.end(), __comp); }
3471 template<
typename _Tp>
3472 _GLIBCXX14_CONSTEXPR
3473 inline pair<_Tp, _Tp>
3474 minmax(initializer_list<_Tp> __l)
3476 pair<const _Tp*, const _Tp*> __p =
3477 std::minmax_element(__l.begin(), __l.end());
3481 template<
typename _Tp,
typename _Compare>
3482 _GLIBCXX14_CONSTEXPR
3483 inline pair<_Tp, _Tp>
3484 minmax(initializer_list<_Tp> __l, _Compare __comp)
3486 pair<const _Tp*, const _Tp*> __p =
3487 std::minmax_element(__l.begin(), __l.end(), __comp);
3491 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3492 typename _BinaryPredicate>
3494 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3495 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3499 for (; __first1 != __last1; ++__first1, (void)++__first2)
3500 if (!__pred(__first1, __first2))
3503 if (__first1 == __last1)
3508 _ForwardIterator2 __last2 = __first2;
3510 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3513 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3517 = std::__count_if(__first2, __last2,
3518 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3519 if (0 == __matches ||
3520 std::__count_if(__scan, __last1,
3521 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3540 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3542 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3543 _ForwardIterator2 __first2)
3546 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3547 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3548 __glibcxx_function_requires(_EqualOpConcept<
3549 typename iterator_traits<_ForwardIterator1>::value_type,
3550 typename iterator_traits<_ForwardIterator2>::value_type>)
3551 __glibcxx_requires_valid_range(__first1, __last1);
3553 return std::__is_permutation(__first1, __last1, __first2,
3554 __gnu_cxx::__ops::__iter_equal_to_iter());
3571 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3572 typename _BinaryPredicate>
3574 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3575 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3578 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3579 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3580 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3581 typename iterator_traits<_ForwardIterator1>::value_type,
3582 typename iterator_traits<_ForwardIterator2>::value_type>)
3583 __glibcxx_requires_valid_range(__first1, __last1);
3585 return std::__is_permutation(__first1, __last1, __first2,
3586 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3589#if __cplusplus > 201103L
3590 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3591 typename _BinaryPredicate>
3593 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3594 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3595 _BinaryPredicate __pred)
3598 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3600 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3601 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3602 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3603 constexpr bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3614 for (; __first1 != __last1 && __first2 != __last2;
3615 ++__first1, (void)++__first2)
3616 if (!__pred(__first1, __first2))
3621 if (__first1 == __last1)
3628 if (__d1 == 0 && __d2 == 0)
3634 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3637 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3640 auto __matches = std::__count_if(__first2, __last2,
3641 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3643 || std::__count_if(__scan, __last1,
3644 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3664 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3666 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3667 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3669 __glibcxx_requires_valid_range(__first1, __last1);
3670 __glibcxx_requires_valid_range(__first2, __last2);
3673 std::__is_permutation(__first1, __last1, __first2, __last2,
3674 __gnu_cxx::__ops::__iter_equal_to_iter());
3691 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3692 typename _BinaryPredicate>
3694 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3695 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3696 _BinaryPredicate __pred)
3698 __glibcxx_requires_valid_range(__first1, __last1);
3699 __glibcxx_requires_valid_range(__first2, __last2);
3701 return std::__is_permutation(__first1, __last1, __first2, __last2,
3702 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3705#if __cplusplus > 201402L
3707#define __cpp_lib_clamp 201603
3717 template<
typename _Tp>
3718 constexpr const _Tp&
3719 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3721 __glibcxx_assert(!(__hi < __lo));
3722 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3735 template<
typename _Tp,
typename _Compare>
3736 constexpr const _Tp&
3737 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3739 __glibcxx_assert(!__comp(__hi, __lo));
3740 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3745#ifdef _GLIBCXX_USE_C99_STDINT_TR1
3767 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3768 pair<_IntType, _IntType>
3770 _UniformRandomBitGenerator&& __g)
3789 template<
typename _RandomAccessIterator,
3790 typename _UniformRandomNumberGenerator>
3792 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3793 _UniformRandomNumberGenerator&& __g)
3796 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3797 _RandomAccessIterator>)
3798 __glibcxx_requires_valid_range(__first, __last);
3800 if (__first == __last)
3803 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3806 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3808 typedef typename __distr_type::param_type __p_type;
3810 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3815 const __uc_type __urngrange = __g.max() - __g.min();
3816 const __uc_type __urange = __uc_type(__last - __first);
3818 if (__urngrange / __urange >= __urange)
3821 _RandomAccessIterator __i = __first + 1;
3827 if ((__urange % 2) == 0)
3829 __distr_type __d{0, 1};
3830 std::iter_swap(__i++, __first + __d(__g));
3837 while (__i != __last)
3839 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3844 std::iter_swap(__i++, __first + __pospos.
first);
3845 std::iter_swap(__i++, __first + __pospos.
second);
3853 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3854 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3860_GLIBCXX_BEGIN_NAMESPACE_ALGO
3874 template<
typename _InputIterator,
typename _Function>
3876 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3879 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3880 __glibcxx_requires_valid_range(__first, __last);
3881 for (; __first != __last; ++__first)
3886#if __cplusplus >= 201703L
3899 template<
typename _InputIterator,
typename _Size,
typename _Function>
3901 for_each_n(_InputIterator __first, _Size __n, _Function __f)
3903 typename iterator_traits<_InputIterator>::difference_type __n2 = __n;
3904 using _Cat =
typename iterator_traits<_InputIterator>::iterator_category;
3905 if constexpr (is_base_of_v<random_access_iterator_tag, _Cat>)
3909 auto __last = __first + __n2;
3910 std::for_each(__first, __last, std::move(__f));
3934 template<
typename _InputIterator,
typename _Tp>
3935 inline _InputIterator
3936 find(_InputIterator __first, _InputIterator __last,
3940 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3941 __glibcxx_function_requires(_EqualOpConcept<
3942 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3943 __glibcxx_requires_valid_range(__first, __last);
3945 __gnu_cxx::__ops::__iter_equals_val(__val));
3958 template<
typename _InputIterator,
typename _Predicate>
3959 inline _InputIterator
3960 find_if(_InputIterator __first, _InputIterator __last,
3964 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3965 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3966 typename iterator_traits<_InputIterator>::value_type>)
3967 __glibcxx_requires_valid_range(__first, __last);
3970 __gnu_cxx::__ops::__pred_iter(__pred));
3989 template<
typename _InputIterator,
typename _ForwardIterator>
3991 find_first_of(_InputIterator __first1, _InputIterator __last1,
3992 _ForwardIterator __first2, _ForwardIterator __last2)
3995 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3996 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3997 __glibcxx_function_requires(_EqualOpConcept<
3998 typename iterator_traits<_InputIterator>::value_type,
3999 typename iterator_traits<_ForwardIterator>::value_type>)
4000 __glibcxx_requires_valid_range(__first1, __last1);
4001 __glibcxx_requires_valid_range(__first2, __last2);
4003 for (; __first1 != __last1; ++__first1)
4004 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4005 if (*__first1 == *__iter)
4029 template<
typename _InputIterator,
typename _ForwardIterator,
4030 typename _BinaryPredicate>
4032 find_first_of(_InputIterator __first1, _InputIterator __last1,
4033 _ForwardIterator __first2, _ForwardIterator __last2,
4034 _BinaryPredicate __comp)
4037 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4038 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4039 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4040 typename iterator_traits<_InputIterator>::value_type,
4041 typename iterator_traits<_ForwardIterator>::value_type>)
4042 __glibcxx_requires_valid_range(__first1, __last1);
4043 __glibcxx_requires_valid_range(__first2, __last2);
4045 for (; __first1 != __last1; ++__first1)
4046 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4047 if (__comp(*__first1, *__iter))
4061 template<
typename _ForwardIterator>
4062 inline _ForwardIterator
4063 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4066 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4067 __glibcxx_function_requires(_EqualityComparableConcept<
4068 typename iterator_traits<_ForwardIterator>::value_type>)
4069 __glibcxx_requires_valid_range(__first, __last);
4071 return std::__adjacent_find(__first, __last,
4072 __gnu_cxx::__ops::__iter_equal_to_iter());
4086 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4087 inline _ForwardIterator
4088 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4089 _BinaryPredicate __binary_pred)
4092 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4093 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4094 typename iterator_traits<_ForwardIterator>::value_type,
4095 typename iterator_traits<_ForwardIterator>::value_type>)
4096 __glibcxx_requires_valid_range(__first, __last);
4098 return std::__adjacent_find(__first, __last,
4099 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4111 template<
typename _InputIterator,
typename _Tp>
4112 inline typename iterator_traits<_InputIterator>::difference_type
4113 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4116 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4117 __glibcxx_function_requires(_EqualOpConcept<
4118 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4119 __glibcxx_requires_valid_range(__first, __last);
4121 return std::__count_if(__first, __last,
4122 __gnu_cxx::__ops::__iter_equals_val(__value));
4134 template<
typename _InputIterator,
typename _Predicate>
4135 inline typename iterator_traits<_InputIterator>::difference_type
4136 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4139 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4140 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4141 typename iterator_traits<_InputIterator>::value_type>)
4142 __glibcxx_requires_valid_range(__first, __last);
4144 return std::__count_if(__first, __last,
4145 __gnu_cxx::__ops::__pred_iter(__pred));
4174 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4175 inline _ForwardIterator1
4176 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4177 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4180 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4181 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4182 __glibcxx_function_requires(_EqualOpConcept<
4183 typename iterator_traits<_ForwardIterator1>::value_type,
4184 typename iterator_traits<_ForwardIterator2>::value_type>)
4185 __glibcxx_requires_valid_range(__first1, __last1);
4186 __glibcxx_requires_valid_range(__first2, __last2);
4188 return std::__search(__first1, __last1, __first2, __last2,
4189 __gnu_cxx::__ops::__iter_equal_to_iter());
4213 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4214 typename _BinaryPredicate>
4215 inline _ForwardIterator1
4216 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4217 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4218 _BinaryPredicate __predicate)
4221 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4222 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4223 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4224 typename iterator_traits<_ForwardIterator1>::value_type,
4225 typename iterator_traits<_ForwardIterator2>::value_type>)
4226 __glibcxx_requires_valid_range(__first1, __last1);
4227 __glibcxx_requires_valid_range(__first2, __last2);
4229 return std::__search(__first1, __last1, __first2, __last2,
4230 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4248 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4249 inline _ForwardIterator
4250 search_n(_ForwardIterator __first, _ForwardIterator __last,
4251 _Integer __count,
const _Tp& __val)
4254 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4255 __glibcxx_function_requires(_EqualOpConcept<
4256 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4257 __glibcxx_requires_valid_range(__first, __last);
4259 return std::__search_n(__first, __last, __count,
4260 __gnu_cxx::__ops::__iter_equals_val(__val));
4281 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4282 typename _BinaryPredicate>
4283 inline _ForwardIterator
4284 search_n(_ForwardIterator __first, _ForwardIterator __last,
4285 _Integer __count,
const _Tp& __val,
4286 _BinaryPredicate __binary_pred)
4289 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4290 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4291 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4292 __glibcxx_requires_valid_range(__first, __last);
4294 return std::__search_n(__first, __last, __count,
4295 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4298#if __cplusplus > 201402L
4306 template<
typename _ForwardIterator,
typename _Searcher>
4307 inline _ForwardIterator
4308 search(_ForwardIterator __first, _ForwardIterator __last,
4309 const _Searcher& __searcher)
4310 {
return __searcher(__first, __last).first; }
4329 template<
typename _InputIterator,
typename _OutputIterator,
4330 typename _UnaryOperation>
4332 transform(_InputIterator __first, _InputIterator __last,
4333 _OutputIterator __result, _UnaryOperation __unary_op)
4336 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4337 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4339 __typeof__(__unary_op(*__first))>)
4340 __glibcxx_requires_valid_range(__first, __last);
4342 for (; __first != __last; ++__first, (void)++__result)
4343 *__result = __unary_op(*__first);
4366 template<
typename _InputIterator1,
typename _InputIterator2,
4367 typename _OutputIterator,
typename _BinaryOperation>
4369 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4370 _InputIterator2 __first2, _OutputIterator __result,
4371 _BinaryOperation __binary_op)
4374 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4375 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4376 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4378 __typeof__(__binary_op(*__first1,*__first2))>)
4379 __glibcxx_requires_valid_range(__first1, __last1);
4381 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4382 *__result = __binary_op(*__first1, *__first2);
4399 template<
typename _ForwardIterator,
typename _Tp>
4401 replace(_ForwardIterator __first, _ForwardIterator __last,
4402 const _Tp& __old_value,
const _Tp& __new_value)
4405 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4407 __glibcxx_function_requires(_EqualOpConcept<
4408 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4409 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4410 typename iterator_traits<_ForwardIterator>::value_type>)
4411 __glibcxx_requires_valid_range(__first, __last);
4413 for (; __first != __last; ++__first)
4414 if (*__first == __old_value)
4415 *__first = __new_value;
4431 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4433 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4434 _Predicate __pred,
const _Tp& __new_value)
4437 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4439 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4440 typename iterator_traits<_ForwardIterator>::value_type>)
4441 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4442 typename iterator_traits<_ForwardIterator>::value_type>)
4443 __glibcxx_requires_valid_range(__first, __last);
4445 for (; __first != __last; ++__first)
4446 if (__pred(*__first))
4447 *__first = __new_value;
4463 template<
typename _ForwardIterator,
typename _Generator>
4465 generate(_ForwardIterator __first, _ForwardIterator __last,
4469 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4470 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4471 typename iterator_traits<_ForwardIterator>::value_type>)
4472 __glibcxx_requires_valid_range(__first, __last);
4474 for (; __first != __last; ++__first)
4494 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4496 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4499 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4501 __typeof__(__gen())>)
4503 for (__decltype(__n + 0) __niter = __n;
4504 __niter > 0; --__niter, (void) ++__first)
4530 template<
typename _InputIterator,
typename _OutputIterator>
4531 inline _OutputIterator
4532 unique_copy(_InputIterator __first, _InputIterator __last,
4533 _OutputIterator __result)
4536 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4537 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4538 typename iterator_traits<_InputIterator>::value_type>)
4539 __glibcxx_function_requires(_EqualityComparableConcept<
4540 typename iterator_traits<_InputIterator>::value_type>)
4541 __glibcxx_requires_valid_range(__first, __last);
4543 if (__first == __last)
4546 __gnu_cxx::__ops::__iter_equal_to_iter(),
4570 template<
typename _InputIterator,
typename _OutputIterator,
4571 typename _BinaryPredicate>
4572 inline _OutputIterator
4573 unique_copy(_InputIterator __first, _InputIterator __last,
4574 _OutputIterator __result,
4575 _BinaryPredicate __binary_pred)
4578 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4579 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4580 typename iterator_traits<_InputIterator>::value_type>)
4581 __glibcxx_requires_valid_range(__first, __last);
4583 if (__first == __last)
4586 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4603 template<
typename _RandomAccessIterator>
4605 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4608 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4609 _RandomAccessIterator>)
4610 __glibcxx_requires_valid_range(__first, __last);
4612 if (__first != __last)
4613 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4616 _RandomAccessIterator __j = __first
4617 + std::rand() % ((__i - __first) + 1);
4619 std::iter_swap(__i, __j);
4638 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4640 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4641#
if __cplusplus >= 201103L
4642 _RandomNumberGenerator&& __rand)
4644 _RandomNumberGenerator& __rand)
4648 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4649 _RandomAccessIterator>)
4650 __glibcxx_requires_valid_range(__first, __last);
4652 if (__first == __last)
4654 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4656 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4658 std::iter_swap(__i, __j);
4678 template<
typename _ForwardIterator,
typename _Predicate>
4679 inline _ForwardIterator
4680 partition(_ForwardIterator __first, _ForwardIterator __last,
4684 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4686 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4687 typename iterator_traits<_ForwardIterator>::value_type>)
4688 __glibcxx_requires_valid_range(__first, __last);
4711 template<
typename _RandomAccessIterator>
4713 partial_sort(_RandomAccessIterator __first,
4714 _RandomAccessIterator __middle,
4715 _RandomAccessIterator __last)
4718 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4719 _RandomAccessIterator>)
4720 __glibcxx_function_requires(_LessThanComparableConcept<
4721 typename iterator_traits<_RandomAccessIterator>::value_type>)
4722 __glibcxx_requires_valid_range(__first, __middle);
4723 __glibcxx_requires_valid_range(__middle, __last);
4724 __glibcxx_requires_irreflexive(__first, __last);
4726 std::__partial_sort(__first, __middle, __last,
4727 __gnu_cxx::__ops::__iter_less_iter());
4749 template<
typename _RandomAccessIterator,
typename _Compare>
4751 partial_sort(_RandomAccessIterator __first,
4752 _RandomAccessIterator __middle,
4753 _RandomAccessIterator __last,
4757 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4758 _RandomAccessIterator>)
4759 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4760 typename iterator_traits<_RandomAccessIterator>::value_type,
4761 typename iterator_traits<_RandomAccessIterator>::value_type>)
4762 __glibcxx_requires_valid_range(__first, __middle);
4763 __glibcxx_requires_valid_range(__middle, __last);
4764 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4766 std::__partial_sort(__first, __middle, __last,
4767 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4785 template<
typename _RandomAccessIterator>
4787 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4788 _RandomAccessIterator __last)
4791 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4792 _RandomAccessIterator>)
4793 __glibcxx_function_requires(_LessThanComparableConcept<
4794 typename iterator_traits<_RandomAccessIterator>::value_type>)
4795 __glibcxx_requires_valid_range(__first, __nth);
4796 __glibcxx_requires_valid_range(__nth, __last);
4797 __glibcxx_requires_irreflexive(__first, __last);
4799 if (__first == __last || __nth == __last)
4802 std::__introselect(__first, __nth, __last,
4804 __gnu_cxx::__ops::__iter_less_iter());
4824 template<
typename _RandomAccessIterator,
typename _Compare>
4826 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4827 _RandomAccessIterator __last, _Compare __comp)
4830 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4831 _RandomAccessIterator>)
4832 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4833 typename iterator_traits<_RandomAccessIterator>::value_type,
4834 typename iterator_traits<_RandomAccessIterator>::value_type>)
4835 __glibcxx_requires_valid_range(__first, __nth);
4836 __glibcxx_requires_valid_range(__nth, __last);
4837 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4839 if (__first == __last || __nth == __last)
4842 std::__introselect(__first, __nth, __last,
4844 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4861 template<
typename _RandomAccessIterator>
4863 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4866 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4867 _RandomAccessIterator>)
4868 __glibcxx_function_requires(_LessThanComparableConcept<
4869 typename iterator_traits<_RandomAccessIterator>::value_type>)
4870 __glibcxx_requires_valid_range(__first, __last);
4871 __glibcxx_requires_irreflexive(__first, __last);
4873 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4891 template<
typename _RandomAccessIterator,
typename _Compare>
4893 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4897 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4898 _RandomAccessIterator>)
4899 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4900 typename iterator_traits<_RandomAccessIterator>::value_type,
4901 typename iterator_traits<_RandomAccessIterator>::value_type>)
4902 __glibcxx_requires_valid_range(__first, __last);
4903 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4905 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4908 template<
typename _InputIterator1,
typename _InputIterator2,
4909 typename _OutputIterator,
typename _Compare>
4911 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4912 _InputIterator2 __first2, _InputIterator2 __last2,
4913 _OutputIterator __result, _Compare __comp)
4915 while (__first1 != __last1 && __first2 != __last2)
4917 if (__comp(__first2, __first1))
4919 *__result = *__first2;
4924 *__result = *__first1;
4929 return std::copy(__first2, __last2,
4930 std::copy(__first1, __last1, __result));
4952 template<
typename _InputIterator1,
typename _InputIterator2,
4953 typename _OutputIterator>
4954 inline _OutputIterator
4955 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4956 _InputIterator2 __first2, _InputIterator2 __last2,
4957 _OutputIterator __result)
4960 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4961 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4962 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4963 typename iterator_traits<_InputIterator1>::value_type>)
4964 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4965 typename iterator_traits<_InputIterator2>::value_type>)
4966 __glibcxx_function_requires(_LessThanOpConcept<
4967 typename iterator_traits<_InputIterator2>::value_type,
4968 typename iterator_traits<_InputIterator1>::value_type>)
4969 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4970 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4971 __glibcxx_requires_irreflexive2(__first1, __last1);
4972 __glibcxx_requires_irreflexive2(__first2, __last2);
4974 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4975 __first2, __last2, __result,
4976 __gnu_cxx::__ops::__iter_less_iter());
5002 template<
typename _InputIterator1,
typename _InputIterator2,
5003 typename _OutputIterator,
typename _Compare>
5004 inline _OutputIterator
5005 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5006 _InputIterator2 __first2, _InputIterator2 __last2,
5007 _OutputIterator __result, _Compare __comp)
5010 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5011 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5012 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5013 typename iterator_traits<_InputIterator1>::value_type>)
5014 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5015 typename iterator_traits<_InputIterator2>::value_type>)
5016 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5017 typename iterator_traits<_InputIterator2>::value_type,
5018 typename iterator_traits<_InputIterator1>::value_type>)
5019 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5020 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5021 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5022 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5024 return _GLIBCXX_STD_A::__merge(__first1, __last1,
5025 __first2, __last2, __result,
5026 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5029 template<
typename _RandomAccessIterator,
typename _Compare>
5031 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5034 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5036 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5039 typedef _Temporary_buffer<_RandomAccessIterator, _ValueType> _TmpBuf;
5042 if (__buf.begin() == 0)
5045 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
5046 _DistanceType(__buf.size()), __comp);
5066 template<
typename _RandomAccessIterator>
5068 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5071 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5072 _RandomAccessIterator>)
5073 __glibcxx_function_requires(_LessThanComparableConcept<
5074 typename iterator_traits<_RandomAccessIterator>::value_type>)
5075 __glibcxx_requires_valid_range(__first, __last);
5076 __glibcxx_requires_irreflexive(__first, __last);
5078 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5079 __gnu_cxx::__ops::__iter_less_iter());
5100 template<
typename _RandomAccessIterator,
typename _Compare>
5102 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5106 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5107 _RandomAccessIterator>)
5108 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5109 typename iterator_traits<_RandomAccessIterator>::value_type,
5110 typename iterator_traits<_RandomAccessIterator>::value_type>)
5111 __glibcxx_requires_valid_range(__first, __last);
5112 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5114 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5115 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5118 template<
typename _InputIterator1,
typename _InputIterator2,
5119 typename _OutputIterator,
5122 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5123 _InputIterator2 __first2, _InputIterator2 __last2,
5124 _OutputIterator __result, _Compare __comp)
5126 while (__first1 != __last1 && __first2 != __last2)
5128 if (__comp(__first1, __first2))
5130 *__result = *__first1;
5133 else if (__comp(__first2, __first1))
5135 *__result = *__first2;
5140 *__result = *__first1;
5146 return std::copy(__first2, __last2,
5147 std::copy(__first1, __last1, __result));
5169 template<
typename _InputIterator1,
typename _InputIterator2,
5170 typename _OutputIterator>
5171 inline _OutputIterator
5172 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5173 _InputIterator2 __first2, _InputIterator2 __last2,
5174 _OutputIterator __result)
5177 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5178 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5179 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5180 typename iterator_traits<_InputIterator1>::value_type>)
5181 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5182 typename iterator_traits<_InputIterator2>::value_type>)
5183 __glibcxx_function_requires(_LessThanOpConcept<
5184 typename iterator_traits<_InputIterator1>::value_type,
5185 typename iterator_traits<_InputIterator2>::value_type>)
5186 __glibcxx_function_requires(_LessThanOpConcept<
5187 typename iterator_traits<_InputIterator2>::value_type,
5188 typename iterator_traits<_InputIterator1>::value_type>)
5189 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5190 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5191 __glibcxx_requires_irreflexive2(__first1, __last1);
5192 __glibcxx_requires_irreflexive2(__first2, __last2);
5194 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5195 __first2, __last2, __result,
5196 __gnu_cxx::__ops::__iter_less_iter());
5219 template<
typename _InputIterator1,
typename _InputIterator2,
5220 typename _OutputIterator,
typename _Compare>
5221 inline _OutputIterator
5222 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5223 _InputIterator2 __first2, _InputIterator2 __last2,
5224 _OutputIterator __result, _Compare __comp)
5227 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5228 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5229 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5230 typename iterator_traits<_InputIterator1>::value_type>)
5231 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5232 typename iterator_traits<_InputIterator2>::value_type>)
5233 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5234 typename iterator_traits<_InputIterator1>::value_type,
5235 typename iterator_traits<_InputIterator2>::value_type>)
5236 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5237 typename iterator_traits<_InputIterator2>::value_type,
5238 typename iterator_traits<_InputIterator1>::value_type>)
5239 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5240 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5241 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5242 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5244 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5245 __first2, __last2, __result,
5246 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5249 template<
typename _InputIterator1,
typename _InputIterator2,
5250 typename _OutputIterator,
5253 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5254 _InputIterator2 __first2, _InputIterator2 __last2,
5255 _OutputIterator __result, _Compare __comp)
5257 while (__first1 != __last1 && __first2 != __last2)
5258 if (__comp(__first1, __first2))
5260 else if (__comp(__first2, __first1))
5264 *__result = *__first1;
5290 template<
typename _InputIterator1,
typename _InputIterator2,
5291 typename _OutputIterator>
5292 inline _OutputIterator
5293 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5294 _InputIterator2 __first2, _InputIterator2 __last2,
5295 _OutputIterator __result)
5298 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5299 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5300 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5301 typename iterator_traits<_InputIterator1>::value_type>)
5302 __glibcxx_function_requires(_LessThanOpConcept<
5303 typename iterator_traits<_InputIterator1>::value_type,
5304 typename iterator_traits<_InputIterator2>::value_type>)
5305 __glibcxx_function_requires(_LessThanOpConcept<
5306 typename iterator_traits<_InputIterator2>::value_type,
5307 typename iterator_traits<_InputIterator1>::value_type>)
5308 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5309 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5310 __glibcxx_requires_irreflexive2(__first1, __last1);
5311 __glibcxx_requires_irreflexive2(__first2, __last2);
5313 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5314 __first2, __last2, __result,
5315 __gnu_cxx::__ops::__iter_less_iter());
5339 template<
typename _InputIterator1,
typename _InputIterator2,
5340 typename _OutputIterator,
typename _Compare>
5341 inline _OutputIterator
5342 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5343 _InputIterator2 __first2, _InputIterator2 __last2,
5344 _OutputIterator __result, _Compare __comp)
5347 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5348 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5349 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5350 typename iterator_traits<_InputIterator1>::value_type>)
5351 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5352 typename iterator_traits<_InputIterator1>::value_type,
5353 typename iterator_traits<_InputIterator2>::value_type>)
5354 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5355 typename iterator_traits<_InputIterator2>::value_type,
5356 typename iterator_traits<_InputIterator1>::value_type>)
5357 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5358 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5359 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5360 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5362 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5363 __first2, __last2, __result,
5364 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5367 template<
typename _InputIterator1,
typename _InputIterator2,
5368 typename _OutputIterator,
5371 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5372 _InputIterator2 __first2, _InputIterator2 __last2,
5373 _OutputIterator __result, _Compare __comp)
5375 while (__first1 != __last1 && __first2 != __last2)
5376 if (__comp(__first1, __first2))
5378 *__result = *__first1;
5382 else if (__comp(__first2, __first1))
5389 return std::copy(__first1, __last1, __result);
5412 template<
typename _InputIterator1,
typename _InputIterator2,
5413 typename _OutputIterator>
5414 inline _OutputIterator
5415 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5416 _InputIterator2 __first2, _InputIterator2 __last2,
5417 _OutputIterator __result)
5420 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5421 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5422 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5423 typename iterator_traits<_InputIterator1>::value_type>)
5424 __glibcxx_function_requires(_LessThanOpConcept<
5425 typename iterator_traits<_InputIterator1>::value_type,
5426 typename iterator_traits<_InputIterator2>::value_type>)
5427 __glibcxx_function_requires(_LessThanOpConcept<
5428 typename iterator_traits<_InputIterator2>::value_type,
5429 typename iterator_traits<_InputIterator1>::value_type>)
5430 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5431 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5432 __glibcxx_requires_irreflexive2(__first1, __last1);
5433 __glibcxx_requires_irreflexive2(__first2, __last2);
5435 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5436 __first2, __last2, __result,
5437 __gnu_cxx::__ops::__iter_less_iter());
5463 template<
typename _InputIterator1,
typename _InputIterator2,
5464 typename _OutputIterator,
typename _Compare>
5465 inline _OutputIterator
5466 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5467 _InputIterator2 __first2, _InputIterator2 __last2,
5468 _OutputIterator __result, _Compare __comp)
5471 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5472 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5473 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5474 typename iterator_traits<_InputIterator1>::value_type>)
5475 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5476 typename iterator_traits<_InputIterator1>::value_type,
5477 typename iterator_traits<_InputIterator2>::value_type>)
5478 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5479 typename iterator_traits<_InputIterator2>::value_type,
5480 typename iterator_traits<_InputIterator1>::value_type>)
5481 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5482 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5483 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5484 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5486 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5487 __first2, __last2, __result,
5488 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5491 template<
typename _InputIterator1,
typename _InputIterator2,
5492 typename _OutputIterator,
5495 __set_symmetric_difference(_InputIterator1 __first1,
5496 _InputIterator1 __last1,
5497 _InputIterator2 __first2,
5498 _InputIterator2 __last2,
5499 _OutputIterator __result,
5502 while (__first1 != __last1 && __first2 != __last2)
5503 if (__comp(__first1, __first2))
5505 *__result = *__first1;
5509 else if (__comp(__first2, __first1))
5511 *__result = *__first2;
5520 return std::copy(__first2, __last2,
5521 std::copy(__first1, __last1, __result));
5542 template<
typename _InputIterator1,
typename _InputIterator2,
5543 typename _OutputIterator>
5544 inline _OutputIterator
5545 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5546 _InputIterator2 __first2, _InputIterator2 __last2,
5547 _OutputIterator __result)
5550 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5551 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5552 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5553 typename iterator_traits<_InputIterator1>::value_type>)
5554 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5555 typename iterator_traits<_InputIterator2>::value_type>)
5556 __glibcxx_function_requires(_LessThanOpConcept<
5557 typename iterator_traits<_InputIterator1>::value_type,
5558 typename iterator_traits<_InputIterator2>::value_type>)
5559 __glibcxx_function_requires(_LessThanOpConcept<
5560 typename iterator_traits<_InputIterator2>::value_type,
5561 typename iterator_traits<_InputIterator1>::value_type>)
5562 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5563 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5564 __glibcxx_requires_irreflexive2(__first1, __last1);
5565 __glibcxx_requires_irreflexive2(__first2, __last2);
5567 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5568 __first2, __last2, __result,
5569 __gnu_cxx::__ops::__iter_less_iter());
5593 template<
typename _InputIterator1,
typename _InputIterator2,
5594 typename _OutputIterator,
typename _Compare>
5595 inline _OutputIterator
5596 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5597 _InputIterator2 __first2, _InputIterator2 __last2,
5598 _OutputIterator __result,
5602 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5603 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5604 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5605 typename iterator_traits<_InputIterator1>::value_type>)
5606 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5607 typename iterator_traits<_InputIterator2>::value_type>)
5608 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5609 typename iterator_traits<_InputIterator1>::value_type,
5610 typename iterator_traits<_InputIterator2>::value_type>)
5611 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5612 typename iterator_traits<_InputIterator2>::value_type,
5613 typename iterator_traits<_InputIterator1>::value_type>)
5614 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5615 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5616 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5617 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5619 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5620 __first2, __last2, __result,
5621 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5624 template<
typename _ForwardIterator,
typename _Compare>
5625 _GLIBCXX14_CONSTEXPR
5627 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5630 if (__first == __last)
5632 _ForwardIterator __result = __first;
5633 while (++__first != __last)
5634 if (__comp(__first, __result))
5646 template<
typename _ForwardIterator>
5647 _GLIBCXX14_CONSTEXPR
5649 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5652 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5653 __glibcxx_function_requires(_LessThanComparableConcept<
5654 typename iterator_traits<_ForwardIterator>::value_type>)
5655 __glibcxx_requires_valid_range(__first, __last);
5656 __glibcxx_requires_irreflexive(__first, __last);
5658 return _GLIBCXX_STD_A::__min_element(__first, __last,
5659 __gnu_cxx::__ops::__iter_less_iter());
5671 template<
typename _ForwardIterator,
typename _Compare>
5672 _GLIBCXX14_CONSTEXPR
5673 inline _ForwardIterator
5674 min_element(_ForwardIterator __first, _ForwardIterator __last,
5678 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5679 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5680 typename iterator_traits<_ForwardIterator>::value_type,
5681 typename iterator_traits<_ForwardIterator>::value_type>)
5682 __glibcxx_requires_valid_range(__first, __last);
5683 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5685 return _GLIBCXX_STD_A::__min_element(__first, __last,
5686 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5689 template<
typename _ForwardIterator,
typename _Compare>
5690 _GLIBCXX14_CONSTEXPR
5692 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5695 if (__first == __last)
return __first;
5696 _ForwardIterator __result = __first;
5697 while (++__first != __last)
5698 if (__comp(__result, __first))
5710 template<
typename _ForwardIterator>
5711 _GLIBCXX14_CONSTEXPR
5712 inline _ForwardIterator
5713 max_element(_ForwardIterator __first, _ForwardIterator __last)
5716 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5717 __glibcxx_function_requires(_LessThanComparableConcept<
5718 typename iterator_traits<_ForwardIterator>::value_type>)
5719 __glibcxx_requires_valid_range(__first, __last);
5720 __glibcxx_requires_irreflexive(__first, __last);
5722 return _GLIBCXX_STD_A::__max_element(__first, __last,
5723 __gnu_cxx::__ops::__iter_less_iter());
5735 template<
typename _ForwardIterator,
typename _Compare>
5736 _GLIBCXX14_CONSTEXPR
5737 inline _ForwardIterator
5738 max_element(_ForwardIterator __first, _ForwardIterator __last,
5742 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5743 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5744 typename iterator_traits<_ForwardIterator>::value_type,
5745 typename iterator_traits<_ForwardIterator>::value_type>)
5746 __glibcxx_requires_valid_range(__first, __last);
5747 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5749 return _GLIBCXX_STD_A::__max_element(__first, __last,
5750 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5753#if __cplusplus >= 201402L
5755 template<
typename _InputIterator,
typename _RandomAccessIterator,
5756 typename _Size,
typename _UniformRandomBitGenerator>
5757 _RandomAccessIterator
5760 _Size __n, _UniformRandomBitGenerator&& __g)
5763 using __param_type =
typename __distrib_type::param_type;
5764 __distrib_type __d{};
5765 _Size __sample_sz = 0;
5766 while (__first != __last && __sample_sz != __n)
5768 __out[__sample_sz++] = *__first;
5771 for (
auto __pop_sz = __sample_sz; __first != __last;
5772 ++__first, (void) ++__pop_sz)
5774 const auto __k = __d(__g, __param_type{0, __pop_sz});
5776 __out[__k] = *__first;
5778 return __out + __sample_sz;
5782 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5783 typename _Size,
typename _UniformRandomBitGenerator>
5785 __sample(_ForwardIterator __first, _ForwardIterator __last,
5787 _OutputIterator __out, _Cat,
5788 _Size __n, _UniformRandomBitGenerator&& __g)
5791 using __param_type =
typename __distrib_type::param_type;
5796 if (__first == __last)
5799 __distrib_type __d{};
5801 __n =
std::min(__n, __unsampled_sz);
5806 const __uc_type __urngrange = __g.max() - __g.min();
5807 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5811 while (__n != 0 && __unsampled_sz >= 2)
5817 if (__p.
first < __n)
5819 *__out++ = *__first;
5825 if (__n == 0)
break;
5830 *__out++ = *__first;
5840 for (; __n != 0; ++__first)
5841 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5843 *__out++ = *__first;
5849#if __cplusplus > 201402L
5850#define __cpp_lib_sample 201603
5852 template<
typename _PopulationIterator,
typename _SampleIterator,
5853 typename _Distance,
typename _UniformRandomBitGenerator>
5855 sample(_PopulationIterator __first, _PopulationIterator __last,
5856 _SampleIterator __out, _Distance __n,
5857 _UniformRandomBitGenerator&& __g)
5859 using __pop_cat =
typename
5860 std::iterator_traits<_PopulationIterator>::iterator_category;
5861 using __samp_cat =
typename
5862 std::iterator_traits<_SampleIterator>::iterator_category;
5865 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5866 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5867 "output range must use a RandomAccessIterator when input range"
5868 " does not meet the ForwardIterator requirements");
5870 static_assert(is_integral<_Distance>::value,
5871 "sample size must be an integer type");
5873 typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5875 __sample(__first, __last, __pop_cat{}, __out, __samp_cat{}, __d,
5876 std::forward<_UniformRandomBitGenerator>(__g));
5881_GLIBCXX_END_NAMESPACE_ALGO
5882_GLIBCXX_END_NAMESPACE_VERSION
typename remove_reference< _Tp >::type remove_reference_t
Alias template for remove_reference.
typename make_unsigned< _Tp >::type make_unsigned_t
Alias template for make_unsigned.
typename common_type< _Tp... >::type common_type_t
Alias template for common_type.
constexpr 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.
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
_GLIBCXX14_CONSTEXPR pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
constexpr iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
ISO C++ entities toplevel namespace is std.
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
_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.
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.
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.
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
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.
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
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.
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
_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...
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
_OutputIterator __sample(_ForwardIterator __first, _ForwardIterator __last, forward_iterator_tag, _OutputIterator __out, _Cat, _Size __n, _UniformRandomBitGenerator &&__g)
Selection sampling algorithm.
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
_ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
void __unguarded_linear_insert(_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 __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_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.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
Marking output iterators.
Forward iterators support a superset of input iterator operations.
Bidirectional iterators support a superset of forward iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
Struct holding two objects of arbitrary type.
_T1 first
second_type is the second bound type
_T2 second
first is a copy of the first object
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...