65 #if __cplusplus >= 201103L 71 namespace std _GLIBCXX_VISIBILITY(default)
73 _GLIBCXX_BEGIN_NAMESPACE_VERSION
76 template<
typename _Iterator,
typename _Compare>
79 _Iterator __c, _Compare __comp)
85 else if (__comp(__a, __c))
90 else if (__comp(__a, __c))
92 else if (__comp(__b, __c))
99 template<
typename _InputIterator,
typename _Predicate>
100 inline _InputIterator
101 __find_if(_InputIterator __first, _InputIterator __last,
104 while (__first != __last && !__pred(__first))
110 template<
typename _RandomAccessIterator,
typename _Predicate>
111 _RandomAccessIterator
112 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
115 typename iterator_traits<_RandomAccessIterator>::difference_type
116 __trip_count = (__last - __first) >> 2;
118 for (; __trip_count > 0; --__trip_count)
137 switch (__last - __first)
157 template<
typename _Iterator,
typename _Predicate>
159 __find_if(_Iterator __first, _Iterator __last, _Predicate __pred)
161 return __find_if(__first, __last, __pred,
166 template<
typename _InputIterator,
typename _Predicate>
167 inline _InputIterator
172 __gnu_cxx::__ops::__negate(__pred),
179 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
183 for (; __len; --__len, ++__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,
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,
370 _BinaryPredicate __comp)
373 __glibcxx_function_requires(_BidirectionalIteratorConcept<
374 _BidirectionalIterator1>)
375 __glibcxx_function_requires(_BidirectionalIteratorConcept<
376 _BidirectionalIterator2>)
381 _RevIterator1 __rlast1(__first1);
382 _RevIterator2 __rlast2(__first2);
383 _RevIterator1 __rresult = std::__search(_RevIterator1(__last1), __rlast1,
384 _RevIterator2(__last2), __rlast2,
387 if (__rresult == __rlast1)
391 _BidirectionalIterator1 __result = __rresult.base();
423 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
424 inline _ForwardIterator1
425 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
426 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
429 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
430 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
431 __glibcxx_function_requires(_EqualOpConcept<
432 typename iterator_traits<_ForwardIterator1>::value_type,
433 typename iterator_traits<_ForwardIterator2>::value_type>)
434 __glibcxx_requires_valid_range(__first1, __last1);
435 __glibcxx_requires_valid_range(__first2, __last2);
437 return std::__find_end(__first1, __last1, __first2, __last2,
440 __gnu_cxx::__ops::__iter_equal_to_iter());
471 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
472 typename _BinaryPredicate>
473 inline _ForwardIterator1
474 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
475 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
476 _BinaryPredicate __comp)
479 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
480 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
481 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
482 typename iterator_traits<_ForwardIterator1>::value_type,
483 typename iterator_traits<_ForwardIterator2>::value_type>)
484 __glibcxx_requires_valid_range(__first1, __last1);
485 __glibcxx_requires_valid_range(__first2, __last2);
487 return std::__find_end(__first1, __last1, __first2, __last2,
490 __gnu_cxx::__ops::__iter_comp_iter(__comp));
493 #if __cplusplus >= 201103L 506 template<
typename _InputIterator,
typename _Predicate>
508 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
523 template<
typename _InputIterator,
typename _Predicate>
525 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
541 template<
typename _InputIterator,
typename _Predicate>
543 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
556 template<
typename _InputIterator,
typename _Predicate>
557 inline _InputIterator
558 find_if_not(_InputIterator __first, _InputIterator __last,
562 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
563 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
564 typename iterator_traits<_InputIterator>::value_type>)
565 __glibcxx_requires_valid_range(__first, __last);
567 __gnu_cxx::__ops::__pred_iter(__pred));
580 template<
typename _InputIterator,
typename _Predicate>
582 is_partitioned(_InputIterator __first, _InputIterator __last,
598 template<
typename _ForwardIterator,
typename _Predicate>
600 partition_point(_ForwardIterator __first, _ForwardIterator __last,
604 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
605 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
606 typename iterator_traits<_ForwardIterator>::value_type>)
609 __glibcxx_requires_valid_range(__first, __last);
611 typedef typename iterator_traits<_ForwardIterator>::difference_type
615 _DistanceType __half;
616 _ForwardIterator __middle;
623 if (__pred(*__middle))
627 __len = __len - __half - 1;
636 template<
typename _InputIterator,
typename _OutputIterator,
639 __remove_copy_if(_InputIterator __first, _InputIterator __last,
640 _OutputIterator __result, _Predicate __pred)
642 for (; __first != __last; ++__first)
643 if (!__pred(__first))
645 *__result = *__first;
665 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
666 inline _OutputIterator
667 remove_copy(_InputIterator __first, _InputIterator __last,
668 _OutputIterator __result,
const _Tp& __value)
671 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
672 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
673 typename iterator_traits<_InputIterator>::value_type>)
674 __glibcxx_function_requires(_EqualOpConcept<
675 typename iterator_traits<_InputIterator>::value_type, _Tp>)
676 __glibcxx_requires_valid_range(__first, __last);
678 return std::__remove_copy_if(__first, __last, __result,
679 __gnu_cxx::__ops::__iter_equals_val(__value));
697 template<
typename _InputIterator,
typename _OutputIterator,
699 inline _OutputIterator
700 remove_copy_if(_InputIterator __first, _InputIterator __last,
701 _OutputIterator __result, _Predicate __pred)
704 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
705 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
706 typename iterator_traits<_InputIterator>::value_type>)
707 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
708 typename iterator_traits<_InputIterator>::value_type>)
709 __glibcxx_requires_valid_range(__first, __last);
711 return std::__remove_copy_if(__first, __last, __result,
712 __gnu_cxx::__ops::__pred_iter(__pred));
715 #if __cplusplus >= 201103L 731 template<
typename _InputIterator,
typename _OutputIterator,
734 copy_if(_InputIterator __first, _InputIterator __last,
735 _OutputIterator __result, _Predicate __pred)
738 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
739 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
740 typename iterator_traits<_InputIterator>::value_type>)
741 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
742 typename iterator_traits<_InputIterator>::value_type>)
743 __glibcxx_requires_valid_range(__first, __last);
745 for (; __first != __last; ++__first)
746 if (__pred(*__first))
748 *__result = *__first;
754 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
756 __copy_n(_InputIterator __first, _Size __n,
763 *__result = *__first;
774 template<
typename _RandomAccessIterator,
typename _Size,
775 typename _OutputIterator>
776 inline _OutputIterator
777 __copy_n(_RandomAccessIterator __first, _Size __n,
779 {
return std::copy(__first, __first + __n, __result); }
794 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
795 inline _OutputIterator
796 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
799 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
800 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
801 typename iterator_traits<_InputIterator>::value_type>)
803 return std::__copy_n(__first, __n, __result,
822 template<
typename _InputIterator,
typename _OutputIterator1,
823 typename _OutputIterator2,
typename _Predicate>
825 partition_copy(_InputIterator __first, _InputIterator __last,
826 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
830 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
831 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
832 typename iterator_traits<_InputIterator>::value_type>)
833 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
834 typename iterator_traits<_InputIterator>::value_type>)
835 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
836 typename iterator_traits<_InputIterator>::value_type>)
837 __glibcxx_requires_valid_range(__first, __last);
839 for (; __first != __last; ++__first)
840 if (__pred(*__first))
842 *__out_true = *__first;
847 *__out_false = *__first;
855 template<
typename _ForwardIterator,
typename _Predicate>
857 __remove_if(_ForwardIterator __first, _ForwardIterator __last,
861 if (__first == __last)
863 _ForwardIterator __result = __first;
865 for (; __first != __last; ++__first)
866 if (!__pred(__first))
868 *__result = _GLIBCXX_MOVE(*__first);
891 template<
typename _ForwardIterator,
typename _Tp>
892 inline _ForwardIterator
893 remove(_ForwardIterator __first, _ForwardIterator __last,
897 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
899 __glibcxx_function_requires(_EqualOpConcept<
900 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
901 __glibcxx_requires_valid_range(__first, __last);
903 return std::__remove_if(__first, __last,
904 __gnu_cxx::__ops::__iter_equals_val(__value));
924 template<
typename _ForwardIterator,
typename _Predicate>
925 inline _ForwardIterator
926 remove_if(_ForwardIterator __first, _ForwardIterator __last,
930 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
932 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
933 typename iterator_traits<_ForwardIterator>::value_type>)
934 __glibcxx_requires_valid_range(__first, __last);
936 return std::__remove_if(__first, __last,
937 __gnu_cxx::__ops::__pred_iter(__pred));
940 template<
typename _ForwardIterator,
typename _BinaryPredicate>
942 __adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
943 _BinaryPredicate __binary_pred)
945 if (__first == __last)
947 _ForwardIterator __next = __first;
948 while (++__next != __last)
950 if (__binary_pred(__first, __next))
957 template<
typename _ForwardIterator,
typename _BinaryPredicate>
959 __unique(_ForwardIterator __first, _ForwardIterator __last,
960 _BinaryPredicate __binary_pred)
963 __first = std::__adjacent_find(__first, __last, __binary_pred);
964 if (__first == __last)
968 _ForwardIterator __dest = __first;
970 while (++__first != __last)
971 if (!__binary_pred(__dest, __first))
972 *++__dest = _GLIBCXX_MOVE(*__first);
990 template<
typename _ForwardIterator>
991 inline _ForwardIterator
992 unique(_ForwardIterator __first, _ForwardIterator __last)
995 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
997 __glibcxx_function_requires(_EqualityComparableConcept<
998 typename iterator_traits<_ForwardIterator>::value_type>)
999 __glibcxx_requires_valid_range(__first, __last);
1001 return std::__unique(__first, __last,
1002 __gnu_cxx::__ops::__iter_equal_to_iter());
1020 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1021 inline _ForwardIterator
1022 unique(_ForwardIterator __first, _ForwardIterator __last,
1023 _BinaryPredicate __binary_pred)
1026 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1028 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1029 typename iterator_traits<_ForwardIterator>::value_type,
1030 typename iterator_traits<_ForwardIterator>::value_type>)
1031 __glibcxx_requires_valid_range(__first, __last);
1033 return std::__unique(__first, __last,
1034 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
1043 template<
typename _ForwardIterator,
typename _OutputIterator,
1044 typename _BinaryPredicate>
1047 _OutputIterator __result, _BinaryPredicate __binary_pred,
1051 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1052 typename iterator_traits<_ForwardIterator>::value_type,
1053 typename iterator_traits<_ForwardIterator>::value_type>)
1055 _ForwardIterator __next = __first;
1056 *__result = *__first;
1057 while (++__next != __last)
1058 if (!__binary_pred(__first, __next))
1061 *++__result = *__first;
1072 template<
typename _InputIterator,
typename _OutputIterator,
1073 typename _BinaryPredicate>
1076 _OutputIterator __result, _BinaryPredicate __binary_pred,
1080 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1081 typename iterator_traits<_InputIterator>::value_type,
1082 typename iterator_traits<_InputIterator>::value_type>)
1084 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1085 __decltype(__gnu_cxx::__ops::__iter_comp_val(__binary_pred))
1087 = __gnu_cxx::__ops::__iter_comp_val(__binary_pred);
1088 *__result = __value;
1089 while (++__first != __last)
1090 if (!__rebound_pred(__first, __value))
1093 *++__result = __value;
1104 template<
typename _InputIterator,
typename _ForwardIterator,
1105 typename _BinaryPredicate>
1108 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1112 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1113 typename iterator_traits<_ForwardIterator>::value_type,
1114 typename iterator_traits<_InputIterator>::value_type>)
1115 *__result = *__first;
1116 while (++__first != __last)
1117 if (!__binary_pred(__result, __first))
1118 *++__result = *__first;
1127 template<
typename _B
idirectionalIterator>
1129 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1133 if (__first == __last || __first == --__last)
1147 template<
typename _RandomAccessIterator>
1149 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1152 if (__first == __last)
1155 while (__first < __last)
1175 template<
typename _B
idirectionalIterator>
1177 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1180 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1181 _BidirectionalIterator>)
1182 __glibcxx_requires_valid_range(__first, __last);
1202 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1204 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1205 _OutputIterator __result)
1208 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1209 _BidirectionalIterator>)
1210 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1211 typename iterator_traits<_BidirectionalIterator>::value_type>)
1212 __glibcxx_requires_valid_range(__first, __last);
1214 while (__first != __last)
1217 *__result = *__last;
1227 template<
typename _Eucl
ideanRingElement>
1228 _EuclideanRingElement
1229 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1233 _EuclideanRingElement __t = __m % __n;
1240 inline namespace _V2
1244 template<
typename _ForwardIterator>
1247 _ForwardIterator __middle,
1248 _ForwardIterator __last,
1251 if (__first == __middle)
1253 else if (__last == __middle)
1256 _ForwardIterator __first2 = __middle;
1262 if (__first == __middle)
1263 __middle = __first2;
1265 while (__first2 != __last);
1267 _ForwardIterator __ret = __first;
1269 __first2 = __middle;
1271 while (__first2 != __last)
1276 if (__first == __middle)
1277 __middle = __first2;
1278 else if (__first2 == __last)
1279 __first2 = __middle;
1285 template<
typename _B
idirectionalIterator>
1286 _BidirectionalIterator
1288 _BidirectionalIterator __middle,
1289 _BidirectionalIterator __last,
1293 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1294 _BidirectionalIterator>)
1296 if (__first == __middle)
1298 else if (__last == __middle)
1304 while (__first != __middle && __middle != __last)
1310 if (__first == __middle)
1323 template<
typename _RandomAccessIterator>
1324 _RandomAccessIterator
1326 _RandomAccessIterator __middle,
1327 _RandomAccessIterator __last,
1331 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1332 _RandomAccessIterator>)
1334 if (__first == __middle)
1336 else if (__last == __middle)
1339 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1341 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1344 _Distance __n = __last - __first;
1345 _Distance __k = __middle - __first;
1347 if (__k == __n - __k)
1353 _RandomAccessIterator __p = __first;
1354 _RandomAccessIterator __ret = __first + (__last - __middle);
1358 if (__k < __n - __k)
1360 if (__is_pod(_ValueType) && __k == 1)
1362 _ValueType __t = _GLIBCXX_MOVE(*__p);
1363 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1364 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1367 _RandomAccessIterator __q = __p + __k;
1368 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1377 std::swap(__n, __k);
1383 if (__is_pod(_ValueType) && __k == 1)
1385 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1386 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1387 *__p = _GLIBCXX_MOVE(__t);
1390 _RandomAccessIterator __q = __p + __n;
1392 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1401 std::swap(__n, __k);
1429 template<
typename _ForwardIterator>
1430 inline _ForwardIterator
1431 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1432 _ForwardIterator __last)
1435 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1437 __glibcxx_requires_valid_range(__first, __middle);
1438 __glibcxx_requires_valid_range(__middle, __last);
1440 return std::__rotate(__first, __middle, __last,
1466 template<
typename _ForwardIterator,
typename _OutputIterator>
1467 inline _OutputIterator
1468 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1469 _ForwardIterator __last, _OutputIterator __result)
1472 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1473 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1474 typename iterator_traits<_ForwardIterator>::value_type>)
1475 __glibcxx_requires_valid_range(__first, __middle);
1476 __glibcxx_requires_valid_range(__middle, __last);
1478 return std::copy(__first, __middle,
1479 std::copy(__middle, __last, __result));
1483 template<
typename _ForwardIterator,
typename _Predicate>
1488 if (__first == __last)
1491 while (__pred(*__first))
1492 if (++__first == __last)
1495 _ForwardIterator __next = __first;
1497 while (++__next != __last)
1498 if (__pred(*__next))
1508 template<
typename _B
idirectionalIterator,
typename _Predicate>
1509 _BidirectionalIterator
1510 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1516 if (__first == __last)
1518 else if (__pred(*__first))
1524 if (__first == __last)
1526 else if (!
bool(__pred(*__last)))
1543 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1547 _ForwardIterator __last,
1548 _Predicate __pred, _Distance __len,
1550 _Distance __buffer_size)
1555 if (__len <= __buffer_size)
1557 _ForwardIterator __result1 = __first;
1558 _Pointer __result2 = __buffer;
1563 *__result2 = _GLIBCXX_MOVE(*__first);
1566 for (; __first != __last; ++__first)
1567 if (__pred(__first))
1569 *__result1 = _GLIBCXX_MOVE(*__first);
1574 *__result2 = _GLIBCXX_MOVE(*__first);
1578 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1582 _ForwardIterator __middle = __first;
1584 _ForwardIterator __left_split =
1586 __len / 2, __buffer,
1591 _Distance __right_len = __len - __len / 2;
1592 _ForwardIterator __right_split =
1599 __buffer, __buffer_size);
1601 std::rotate(__left_split, __middle, __right_split);
1603 return __left_split;
1606 template<
typename _ForwardIterator,
typename _Predicate>
1608 __stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1613 if (__first == __last)
1616 typedef typename iterator_traits<_ForwardIterator>::value_type
1618 typedef typename iterator_traits<_ForwardIterator>::difference_type
1626 _DistanceType(__buf.
size()));
1646 template<
typename _ForwardIterator,
typename _Predicate>
1647 inline _ForwardIterator
1648 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1652 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1654 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1655 typename iterator_traits<_ForwardIterator>::value_type>)
1656 __glibcxx_requires_valid_range(__first, __last);
1658 return std::__stable_partition(__first, __last,
1659 __gnu_cxx::__ops::__pred_iter(__pred));
1663 template<
typename _RandomAccessIterator,
typename _Compare>
1666 _RandomAccessIterator __middle,
1667 _RandomAccessIterator __last, _Compare __comp)
1669 std::__make_heap(__first, __middle, __comp);
1670 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1671 if (__comp(__i, __first))
1672 std::__pop_heap(__first, __middle, __i, __comp);
1677 template<
typename _InputIterator,
typename _RandomAccessIterator,
1679 _RandomAccessIterator
1680 __partial_sort_copy(_InputIterator __first, _InputIterator __last,
1681 _RandomAccessIterator __result_first,
1682 _RandomAccessIterator __result_last,
1685 typedef typename iterator_traits<_InputIterator>::value_type
1687 typedef iterator_traits<_RandomAccessIterator> _RItTraits;
1688 typedef typename _RItTraits::difference_type _DistanceType;
1690 if (__result_first == __result_last)
1691 return __result_last;
1692 _RandomAccessIterator __result_real_last = __result_first;
1693 while (__first != __last && __result_real_last != __result_last)
1695 *__result_real_last = *__first;
1696 ++__result_real_last;
1700 std::__make_heap(__result_first, __result_real_last, __comp);
1701 while (__first != __last)
1703 if (__comp(__first, __result_first))
1704 std::__adjust_heap(__result_first, _DistanceType(0),
1705 _DistanceType(__result_real_last
1707 _InputValueType(*__first), __comp);
1710 std::__sort_heap(__result_first, __result_real_last, __comp);
1711 return __result_real_last;
1732 template<
typename _InputIterator,
typename _RandomAccessIterator>
1733 inline _RandomAccessIterator
1734 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1735 _RandomAccessIterator __result_first,
1736 _RandomAccessIterator __result_last)
1738 #ifdef _GLIBCXX_CONCEPT_CHECKS 1739 typedef typename iterator_traits<_InputIterator>::value_type
1741 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1746 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1747 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1749 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1751 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1752 __glibcxx_requires_valid_range(__first, __last);
1753 __glibcxx_requires_irreflexive(__first, __last);
1754 __glibcxx_requires_valid_range(__result_first, __result_last);
1756 return std::__partial_sort_copy(__first, __last,
1757 __result_first, __result_last,
1758 __gnu_cxx::__ops::__iter_less_iter());
1781 template<
typename _InputIterator,
typename _RandomAccessIterator,
1783 inline _RandomAccessIterator
1784 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1785 _RandomAccessIterator __result_first,
1786 _RandomAccessIterator __result_last,
1789 #ifdef _GLIBCXX_CONCEPT_CHECKS 1790 typedef typename iterator_traits<_InputIterator>::value_type
1792 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1797 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1798 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1799 _RandomAccessIterator>)
1800 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1802 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1803 _InputValueType, _OutputValueType>)
1804 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
1805 _OutputValueType, _OutputValueType>)
1806 __glibcxx_requires_valid_range(__first, __last);
1807 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
1808 __glibcxx_requires_valid_range(__result_first, __result_last);
1810 return std::__partial_sort_copy(__first, __last,
1811 __result_first, __result_last,
1812 __gnu_cxx::__ops::__iter_comp_iter(__comp));
1816 template<
typename _RandomAccessIterator,
typename _Compare>
1821 typename iterator_traits<_RandomAccessIterator>::value_type
1822 __val = _GLIBCXX_MOVE(*__last);
1823 _RandomAccessIterator __next = __last;
1825 while (__comp(__val, __next))
1827 *__last = _GLIBCXX_MOVE(*__next);
1831 *__last = _GLIBCXX_MOVE(__val);
1835 template<
typename _RandomAccessIterator,
typename _Compare>
1838 _RandomAccessIterator __last, _Compare __comp)
1840 if (__first == __last)
return;
1842 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
1844 if (__comp(__i, __first))
1846 typename iterator_traits<_RandomAccessIterator>::value_type
1847 __val = _GLIBCXX_MOVE(*__i);
1848 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
1849 *__first = _GLIBCXX_MOVE(__val);
1853 __gnu_cxx::__ops::__val_comp_iter(__comp));
1858 template<
typename _RandomAccessIterator,
typename _Compare>
1861 _RandomAccessIterator __last, _Compare __comp)
1863 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
1865 __gnu_cxx::__ops::__val_comp_iter(__comp));
1872 enum { _S_threshold = 16 };
1875 template<
typename _RandomAccessIterator,
typename _Compare>
1878 _RandomAccessIterator __last, _Compare __comp)
1880 if (__last - __first >
int(_S_threshold))
1891 template<
typename _RandomAccessIterator,
typename _Compare>
1892 _RandomAccessIterator
1894 _RandomAccessIterator __last,
1895 _RandomAccessIterator __pivot, _Compare __comp)
1899 while (__comp(__first, __pivot))
1902 while (__comp(__pivot, __last))
1904 if (!(__first < __last))
1912 template<
typename _RandomAccessIterator,
typename _Compare>
1913 inline _RandomAccessIterator
1915 _RandomAccessIterator __last, _Compare __comp)
1917 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
1923 template<
typename _RandomAccessIterator,
typename _Compare>
1925 __partial_sort(_RandomAccessIterator __first,
1926 _RandomAccessIterator __middle,
1927 _RandomAccessIterator __last,
1931 std::__sort_heap(__first, __middle, __comp);
1935 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1938 _RandomAccessIterator __last,
1939 _Size __depth_limit, _Compare __comp)
1941 while (__last - __first >
int(_S_threshold))
1943 if (__depth_limit == 0)
1945 std::__partial_sort(__first, __last, __last, __comp);
1949 _RandomAccessIterator __cut =
1958 template<
typename _RandomAccessIterator,
typename _Compare>
1960 __sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
1963 if (__first != __last)
1972 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
1974 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
1975 _RandomAccessIterator __last, _Size __depth_limit,
1978 while (__last - __first > 3)
1980 if (__depth_limit == 0)
1988 _RandomAccessIterator __cut =
2018 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2019 inline _ForwardIterator
2020 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2021 const _Tp& __val, _Compare __comp)
2024 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2025 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2026 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2027 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2030 return std::__lower_bound(__first, __last, __val,
2031 __gnu_cxx::__ops::__iter_comp_val(__comp));
2034 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2036 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2037 const _Tp& __val, _Compare __comp)
2039 typedef typename iterator_traits<_ForwardIterator>::difference_type
2046 _DistanceType __half = __len >> 1;
2047 _ForwardIterator __middle = __first;
2049 if (__comp(__val, __middle))
2055 __len = __len - __half - 1;
2072 template<
typename _ForwardIterator,
typename _Tp>
2073 inline _ForwardIterator
2074 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2078 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2079 __glibcxx_function_requires(_LessThanOpConcept<
2080 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2081 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2083 return std::__upper_bound(__first, __last, __val,
2084 __gnu_cxx::__ops::__val_less_iter());
2102 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2103 inline _ForwardIterator
2104 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2105 const _Tp& __val, _Compare __comp)
2108 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2109 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2110 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2111 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2114 return std::__upper_bound(__first, __last, __val,
2115 __gnu_cxx::__ops::__val_comp_iter(__comp));
2118 template<
typename _ForwardIterator,
typename _Tp,
2119 typename _CompareItTp,
typename _CompareTpIt>
2121 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2123 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2125 typedef typename iterator_traits<_ForwardIterator>::difference_type
2132 _DistanceType __half = __len >> 1;
2133 _ForwardIterator __middle = __first;
2135 if (__comp_it_val(__middle, __val))
2139 __len = __len - __half - 1;
2141 else if (__comp_val_it(__val, __middle))
2145 _ForwardIterator __left
2146 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2148 _ForwardIterator __right
2149 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2173 template<
typename _ForwardIterator,
typename _Tp>
2175 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2179 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2180 __glibcxx_function_requires(_LessThanOpConcept<
2181 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2182 __glibcxx_function_requires(_LessThanOpConcept<
2183 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2184 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2185 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2187 return std::__equal_range(__first, __last, __val,
2188 __gnu_cxx::__ops::__iter_less_val(),
2189 __gnu_cxx::__ops::__val_less_iter());
2209 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2211 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2212 const _Tp& __val, _Compare __comp)
2215 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2216 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2217 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2218 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2219 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2220 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2222 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2225 return std::__equal_range(__first, __last, __val,
2226 __gnu_cxx::__ops::__iter_comp_val(__comp),
2227 __gnu_cxx::__ops::__val_comp_iter(__comp));
2242 template<
typename _ForwardIterator,
typename _Tp>
2244 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2248 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2249 __glibcxx_function_requires(_LessThanOpConcept<
2250 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2251 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2252 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2254 _ForwardIterator __i
2255 = std::__lower_bound(__first, __last, __val,
2256 __gnu_cxx::__ops::__iter_less_val());
2257 return __i != __last && !(__val < *__i);
2275 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2277 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2278 const _Tp& __val, _Compare __comp)
2281 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2282 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2283 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2284 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2286 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2289 _ForwardIterator __i
2290 = std::__lower_bound(__first, __last, __val,
2291 __gnu_cxx::__ops::__iter_comp_val(__comp));
2292 return __i != __last && !bool(__comp(__val, *__i));
2298 template<
typename _InputIterator1,
typename _InputIterator2,
2299 typename _OutputIterator,
typename _Compare>
2302 _InputIterator2 __first2, _InputIterator2 __last2,
2303 _OutputIterator __result, _Compare __comp)
2305 while (__first1 != __last1 && __first2 != __last2)
2307 if (__comp(__first2, __first1))
2309 *__result = _GLIBCXX_MOVE(*__first2);
2314 *__result = _GLIBCXX_MOVE(*__first1);
2319 if (__first1 != __last1)
2320 _GLIBCXX_MOVE3(__first1, __last1, __result);
2324 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2325 typename _BidirectionalIterator3,
typename _Compare>
2328 _BidirectionalIterator1 __last1,
2329 _BidirectionalIterator2 __first2,
2330 _BidirectionalIterator2 __last2,
2331 _BidirectionalIterator3 __result,
2334 if (__first1 == __last1)
2336 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2339 else if (__first2 == __last2)
2346 if (__comp(__last2, __last1))
2348 *--__result = _GLIBCXX_MOVE(*__last1);
2349 if (__first1 == __last1)
2351 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2358 *--__result = _GLIBCXX_MOVE(*__last2);
2359 if (__first2 == __last2)
2367 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2369 _BidirectionalIterator1
2371 _BidirectionalIterator1 __middle,
2372 _BidirectionalIterator1 __last,
2373 _Distance __len1, _Distance __len2,
2374 _BidirectionalIterator2 __buffer,
2375 _Distance __buffer_size)
2377 _BidirectionalIterator2 __buffer_end;
2378 if (__len1 > __len2 && __len2 <= __buffer_size)
2382 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2383 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2384 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2389 else if (__len1 <= __buffer_size)
2393 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2394 _GLIBCXX_MOVE3(__middle, __last, __first);
2395 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2409 template<
typename _BidirectionalIterator,
typename _Distance,
2410 typename _Pointer,
typename _Compare>
2413 _BidirectionalIterator __middle,
2414 _BidirectionalIterator __last,
2415 _Distance __len1, _Distance __len2,
2416 _Pointer __buffer, _Distance __buffer_size,
2419 if (__len1 <= __len2 && __len1 <= __buffer_size)
2421 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2425 else if (__len2 <= __buffer_size)
2427 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2429 __buffer_end, __last, __comp);
2433 _BidirectionalIterator __first_cut = __first;
2434 _BidirectionalIterator __second_cut = __middle;
2435 _Distance __len11 = 0;
2436 _Distance __len22 = 0;
2437 if (__len1 > __len2)
2439 __len11 = __len1 / 2;
2442 = std::__lower_bound(__middle, __last, *__first_cut,
2443 __gnu_cxx::__ops::__iter_comp_val(__comp));
2448 __len22 = __len2 / 2;
2451 = std::__upper_bound(__first, __middle, *__second_cut,
2452 __gnu_cxx::__ops::__val_comp_iter(__comp));
2456 _BidirectionalIterator __new_middle
2458 __len1 - __len11, __len22, __buffer,
2461 __len22, __buffer, __buffer_size, __comp);
2464 __len2 - __len22, __buffer,
2465 __buffer_size, __comp);
2470 template<
typename _BidirectionalIterator,
typename _Distance,
2474 _BidirectionalIterator __middle,
2475 _BidirectionalIterator __last,
2476 _Distance __len1, _Distance __len2,
2479 if (__len1 == 0 || __len2 == 0)
2482 if (__len1 + __len2 == 2)
2484 if (__comp(__middle, __first))
2489 _BidirectionalIterator __first_cut = __first;
2490 _BidirectionalIterator __second_cut = __middle;
2491 _Distance __len11 = 0;
2492 _Distance __len22 = 0;
2493 if (__len1 > __len2)
2495 __len11 = __len1 / 2;
2498 = std::__lower_bound(__middle, __last, *__first_cut,
2499 __gnu_cxx::__ops::__iter_comp_val(__comp));
2504 __len22 = __len2 / 2;
2507 = std::__upper_bound(__first, __middle, *__second_cut,
2508 __gnu_cxx::__ops::__val_comp_iter(__comp));
2513 _BidirectionalIterator __new_middle = __first_cut;
2516 __len11, __len22, __comp);
2518 __len1 - __len11, __len2 - __len22, __comp);
2521 template<
typename _B
idirectionalIterator,
typename _Compare>
2523 __inplace_merge(_BidirectionalIterator __first,
2524 _BidirectionalIterator __middle,
2525 _BidirectionalIterator __last,
2528 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2530 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2533 if (__first == __middle || __middle == __last)
2536 const _DistanceType __len1 =
std::distance(__first, __middle);
2537 const _DistanceType __len2 =
std::distance(__middle, __last);
2540 _TmpBuf __buf(__first, __last);
2542 if (__buf.begin() == 0)
2544 (__first, __middle, __last, __len1, __len2, __comp);
2547 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2548 _DistanceType(__buf.size()), __comp);
2569 template<
typename _B
idirectionalIterator>
2571 inplace_merge(_BidirectionalIterator __first,
2572 _BidirectionalIterator __middle,
2573 _BidirectionalIterator __last)
2576 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2577 _BidirectionalIterator>)
2578 __glibcxx_function_requires(_LessThanComparableConcept<
2579 typename iterator_traits<_BidirectionalIterator>::value_type>)
2580 __glibcxx_requires_sorted(__first, __middle);
2581 __glibcxx_requires_sorted(__middle, __last);
2582 __glibcxx_requires_irreflexive(__first, __last);
2584 std::__inplace_merge(__first, __middle, __last,
2585 __gnu_cxx::__ops::__iter_less_iter());
2610 template<
typename _B
idirectionalIterator,
typename _Compare>
2612 inplace_merge(_BidirectionalIterator __first,
2613 _BidirectionalIterator __middle,
2614 _BidirectionalIterator __last,
2618 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2619 _BidirectionalIterator>)
2620 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2621 typename iterator_traits<_BidirectionalIterator>::value_type,
2622 typename iterator_traits<_BidirectionalIterator>::value_type>)
2623 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2624 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2625 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2627 std::__inplace_merge(__first, __middle, __last,
2628 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2633 template<
typename _InputIterator,
typename _OutputIterator,
2637 _InputIterator __first2, _InputIterator __last2,
2638 _OutputIterator __result, _Compare __comp)
2640 while (__first1 != __last1 && __first2 != __last2)
2642 if (__comp(__first2, __first1))
2644 *__result = _GLIBCXX_MOVE(*__first2);
2649 *__result = _GLIBCXX_MOVE(*__first1);
2654 return _GLIBCXX_MOVE3(__first2, __last2,
2655 _GLIBCXX_MOVE3(__first1, __last1,
2659 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2660 typename _Distance,
typename _Compare>
2662 __merge_sort_loop(_RandomAccessIterator1 __first,
2663 _RandomAccessIterator1 __last,
2664 _RandomAccessIterator2 __result, _Distance __step_size,
2667 const _Distance __two_step = 2 * __step_size;
2669 while (__last - __first >= __two_step)
2672 __first + __step_size,
2673 __first + __two_step,
2675 __first += __two_step;
2677 __step_size =
std::min(_Distance(__last - __first), __step_size);
2680 __first + __step_size, __last, __result, __comp);
2683 template<
typename _RandomAccessIterator,
typename _Distance,
2686 __chunk_insertion_sort(_RandomAccessIterator __first,
2687 _RandomAccessIterator __last,
2688 _Distance __chunk_size, _Compare __comp)
2690 while (__last - __first >= __chunk_size)
2693 __first += __chunk_size;
2698 enum { _S_chunk_size = 7 };
2700 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2702 __merge_sort_with_buffer(_RandomAccessIterator __first,
2703 _RandomAccessIterator __last,
2704 _Pointer __buffer, _Compare __comp)
2706 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2709 const _Distance __len = __last - __first;
2710 const _Pointer __buffer_last = __buffer + __len;
2712 _Distance __step_size = _S_chunk_size;
2713 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2715 while (__step_size < __len)
2717 std::__merge_sort_loop(__first, __last, __buffer,
2718 __step_size, __comp);
2720 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2721 __step_size, __comp);
2726 template<
typename _RandomAccessIterator,
typename _Pointer,
2727 typename _Distance,
typename _Compare>
2729 __stable_sort_adaptive(_RandomAccessIterator __first,
2730 _RandomAccessIterator __last,
2731 _Pointer __buffer, _Distance __buffer_size,
2734 const _Distance __len = (__last - __first + 1) / 2;
2735 const _RandomAccessIterator __middle = __first + __len;
2736 if (__len > __buffer_size)
2738 std::__stable_sort_adaptive(__first, __middle, __buffer,
2739 __buffer_size, __comp);
2740 std::__stable_sort_adaptive(__middle, __last, __buffer,
2741 __buffer_size, __comp);
2745 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2746 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2749 _Distance(__middle - __first),
2750 _Distance(__last - __middle),
2751 __buffer, __buffer_size,
2756 template<
typename _RandomAccessIterator,
typename _Compare>
2759 _RandomAccessIterator __last, _Compare __comp)
2761 if (__last - __first < 15)
2766 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2782 template<
typename _InputIterator1,
typename _InputIterator2,
2785 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2786 _InputIterator2 __first2, _InputIterator2 __last2,
2789 while (__first1 != __last1 && __first2 != __last2)
2790 if (__comp(__first2, __first1))
2792 else if (__comp(__first1, __first2))
2800 return __first2 == __last2;
2821 template<
typename _InputIterator1,
typename _InputIterator2>
2823 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2824 _InputIterator2 __first2, _InputIterator2 __last2)
2827 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2828 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2829 __glibcxx_function_requires(_LessThanOpConcept<
2830 typename iterator_traits<_InputIterator1>::value_type,
2831 typename iterator_traits<_InputIterator2>::value_type>)
2832 __glibcxx_function_requires(_LessThanOpConcept<
2833 typename iterator_traits<_InputIterator2>::value_type,
2834 typename iterator_traits<_InputIterator1>::value_type>)
2835 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2836 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2837 __glibcxx_requires_irreflexive2(__first1, __last1);
2838 __glibcxx_requires_irreflexive2(__first2, __last2);
2840 return std::__includes(__first1, __last1, __first2, __last2,
2841 __gnu_cxx::__ops::__iter_less_iter());
2865 template<
typename _InputIterator1,
typename _InputIterator2,
2868 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2869 _InputIterator2 __first2, _InputIterator2 __last2,
2873 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2874 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2875 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2876 typename iterator_traits<_InputIterator1>::value_type,
2877 typename iterator_traits<_InputIterator2>::value_type>)
2878 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2879 typename iterator_traits<_InputIterator2>::value_type,
2880 typename iterator_traits<_InputIterator1>::value_type>)
2881 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2882 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2883 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2884 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2886 return std::__includes(__first1, __last1, __first2, __last2,
2887 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2900 template<
typename _B
idirectionalIterator,
typename _Compare>
2902 __next_permutation(_BidirectionalIterator __first,
2903 _BidirectionalIterator __last, _Compare __comp)
2905 if (__first == __last)
2907 _BidirectionalIterator __i = __first;
2916 _BidirectionalIterator __ii = __i;
2918 if (__comp(__i, __ii))
2920 _BidirectionalIterator __j = __last;
2921 while (!__comp(__i, --__j))
2949 template<
typename _B
idirectionalIterator>
2951 next_permutation(_BidirectionalIterator __first,
2952 _BidirectionalIterator __last)
2955 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2956 _BidirectionalIterator>)
2957 __glibcxx_function_requires(_LessThanComparableConcept<
2958 typename iterator_traits<_BidirectionalIterator>::value_type>)
2959 __glibcxx_requires_valid_range(__first, __last);
2960 __glibcxx_requires_irreflexive(__first, __last);
2962 return std::__next_permutation
2963 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2981 template<
typename _B
idirectionalIterator,
typename _Compare>
2983 next_permutation(_BidirectionalIterator __first,
2984 _BidirectionalIterator __last, _Compare __comp)
2987 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2988 _BidirectionalIterator>)
2989 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2990 typename iterator_traits<_BidirectionalIterator>::value_type,
2991 typename iterator_traits<_BidirectionalIterator>::value_type>)
2992 __glibcxx_requires_valid_range(__first, __last);
2993 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2995 return std::__next_permutation
2996 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
2999 template<
typename _B
idirectionalIterator,
typename _Compare>
3001 __prev_permutation(_BidirectionalIterator __first,
3002 _BidirectionalIterator __last, _Compare __comp)
3004 if (__first == __last)
3006 _BidirectionalIterator __i = __first;
3015 _BidirectionalIterator __ii = __i;
3017 if (__comp(__ii, __i))
3019 _BidirectionalIterator __j = __last;
3020 while (!__comp(--__j, __i))
3049 template<
typename _B
idirectionalIterator>
3051 prev_permutation(_BidirectionalIterator __first,
3052 _BidirectionalIterator __last)
3055 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3056 _BidirectionalIterator>)
3057 __glibcxx_function_requires(_LessThanComparableConcept<
3058 typename iterator_traits<_BidirectionalIterator>::value_type>)
3059 __glibcxx_requires_valid_range(__first, __last);
3060 __glibcxx_requires_irreflexive(__first, __last);
3062 return std::__prev_permutation(__first, __last,
3063 __gnu_cxx::__ops::__iter_less_iter());
3081 template<
typename _B
idirectionalIterator,
typename _Compare>
3083 prev_permutation(_BidirectionalIterator __first,
3084 _BidirectionalIterator __last, _Compare __comp)
3087 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3088 _BidirectionalIterator>)
3089 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3090 typename iterator_traits<_BidirectionalIterator>::value_type,
3091 typename iterator_traits<_BidirectionalIterator>::value_type>)
3092 __glibcxx_requires_valid_range(__first, __last);
3093 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3095 return std::__prev_permutation(__first, __last,
3096 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3102 template<
typename _InputIterator,
typename _OutputIterator,
3103 typename _Predicate,
typename _Tp>
3105 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3106 _OutputIterator __result,
3107 _Predicate __pred,
const _Tp& __new_value)
3109 for (; __first != __last; ++__first, (void)++__result)
3110 if (__pred(__first))
3111 *__result = __new_value;
3113 *__result = *__first;
3131 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3132 inline _OutputIterator
3133 replace_copy(_InputIterator __first, _InputIterator __last,
3134 _OutputIterator __result,
3135 const _Tp& __old_value,
const _Tp& __new_value)
3138 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3139 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3140 typename iterator_traits<_InputIterator>::value_type>)
3141 __glibcxx_function_requires(_EqualOpConcept<
3142 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3143 __glibcxx_requires_valid_range(__first, __last);
3145 return std::__replace_copy_if(__first, __last, __result,
3146 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3165 template<
typename _InputIterator,
typename _OutputIterator,
3166 typename _Predicate,
typename _Tp>
3167 inline _OutputIterator
3168 replace_copy_if(_InputIterator __first, _InputIterator __last,
3169 _OutputIterator __result,
3170 _Predicate __pred,
const _Tp& __new_value)
3173 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3174 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3175 typename iterator_traits<_InputIterator>::value_type>)
3176 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3177 typename iterator_traits<_InputIterator>::value_type>)
3178 __glibcxx_requires_valid_range(__first, __last);
3180 return std::__replace_copy_if(__first, __last, __result,
3181 __gnu_cxx::__ops::__pred_iter(__pred),
3185 template<
typename _InputIterator,
typename _Predicate>
3186 typename iterator_traits<_InputIterator>::difference_type
3187 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3189 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3190 for (; __first != __last; ++__first)
3191 if (__pred(__first))
3196 #if __cplusplus >= 201103L 3204 template<
typename _ForwardIterator>
3206 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3218 template<
typename _ForwardIterator,
typename _Compare>
3220 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3224 template<
typename _ForwardIterator,
typename _Compare>
3226 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3229 if (__first == __last)
3232 _ForwardIterator __next = __first;
3233 for (++__next; __next != __last; __first = __next, (void)++__next)
3234 if (__comp(__next, __first))
3247 template<
typename _ForwardIterator>
3248 inline _ForwardIterator
3249 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3252 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3253 __glibcxx_function_requires(_LessThanComparableConcept<
3254 typename iterator_traits<_ForwardIterator>::value_type>)
3255 __glibcxx_requires_valid_range(__first, __last);
3256 __glibcxx_requires_irreflexive(__first, __last);
3258 return std::__is_sorted_until(__first, __last,
3259 __gnu_cxx::__ops::__iter_less_iter());
3271 template<
typename _ForwardIterator,
typename _Compare>
3272 inline _ForwardIterator
3273 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3277 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3278 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3279 typename iterator_traits<_ForwardIterator>::value_type,
3280 typename iterator_traits<_ForwardIterator>::value_type>)
3281 __glibcxx_requires_valid_range(__first, __last);
3282 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3284 return std::__is_sorted_until(__first, __last,
3285 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3296 template<
typename _Tp>
3297 _GLIBCXX14_CONSTEXPR
3302 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3304 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3317 template<
typename _Tp,
typename _Compare>
3318 _GLIBCXX14_CONSTEXPR
3320 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3326 template<
typename _ForwardIterator,
typename _Compare>
3327 _GLIBCXX14_CONSTEXPR
3329 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3332 _ForwardIterator __next = __first;
3333 if (__first == __last
3334 || ++__next == __last)
3337 _ForwardIterator __min{}, __max{};
3338 if (__comp(__next, __first))
3352 while (__first != __last)
3355 if (++__next == __last)
3357 if (__comp(__first, __min))
3359 else if (!__comp(__first, __max))
3364 if (__comp(__next, __first))
3366 if (__comp(__next, __min))
3368 if (!__comp(__first, __max))
3373 if (__comp(__first, __min))
3375 if (!__comp(__next, __max))
3397 template<
typename _ForwardIterator>
3398 _GLIBCXX14_CONSTEXPR
3400 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3403 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3404 __glibcxx_function_requires(_LessThanComparableConcept<
3405 typename iterator_traits<_ForwardIterator>::value_type>)
3406 __glibcxx_requires_valid_range(__first, __last);
3407 __glibcxx_requires_irreflexive(__first, __last);
3409 return std::__minmax_element(__first, __last,
3410 __gnu_cxx::__ops::__iter_less_iter());
3425 template<
typename _ForwardIterator,
typename _Compare>
3426 _GLIBCXX14_CONSTEXPR
3428 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3432 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3433 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3434 typename iterator_traits<_ForwardIterator>::value_type,
3435 typename iterator_traits<_ForwardIterator>::value_type>)
3436 __glibcxx_requires_valid_range(__first, __last);
3437 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3439 return std::__minmax_element(__first, __last,
3440 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3444 template<
typename _Tp>
3445 _GLIBCXX14_CONSTEXPR
3450 template<
typename _Tp,
typename _Compare>
3451 _GLIBCXX14_CONSTEXPR
3456 template<
typename _Tp>
3457 _GLIBCXX14_CONSTEXPR
3462 template<
typename _Tp,
typename _Compare>
3463 _GLIBCXX14_CONSTEXPR
3468 template<
typename _Tp>
3469 _GLIBCXX14_CONSTEXPR
3478 template<
typename _Tp,
typename _Compare>
3479 _GLIBCXX14_CONSTEXPR
3488 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3489 typename _BinaryPredicate>
3491 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3492 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3496 for (; __first1 != __last1; ++__first1, (void)++__first2)
3497 if (!__pred(__first1, __first2))
3500 if (__first1 == __last1)
3505 _ForwardIterator2 __last2 = __first2;
3507 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3510 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3514 = std::__count_if(__first2, __last2,
3515 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3516 if (0 == __matches ||
3517 std::__count_if(__scan, __last1,
3518 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3537 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3539 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3540 _ForwardIterator2 __first2)
3543 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3544 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3545 __glibcxx_function_requires(_EqualOpConcept<
3546 typename iterator_traits<_ForwardIterator1>::value_type,
3547 typename iterator_traits<_ForwardIterator2>::value_type>)
3548 __glibcxx_requires_valid_range(__first1, __last1);
3550 return std::__is_permutation(__first1, __last1, __first2,
3551 __gnu_cxx::__ops::__iter_equal_to_iter());
3568 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3569 typename _BinaryPredicate>
3571 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3572 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3575 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3576 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3577 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3578 typename iterator_traits<_ForwardIterator1>::value_type,
3579 typename iterator_traits<_ForwardIterator2>::value_type>)
3580 __glibcxx_requires_valid_range(__first1, __last1);
3582 return std::__is_permutation(__first1, __last1, __first2,
3583 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3586 #if __cplusplus > 201103L 3587 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3588 typename _BinaryPredicate>
3590 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3591 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3592 _BinaryPredicate __pred)
3595 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3597 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3598 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3599 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3600 constexpr
bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3611 for (; __first1 != __last1 && __first2 != __last2;
3612 ++__first1, (void)++__first2)
3613 if (!__pred(__first1, __first2))
3618 if (__first1 == __last1)
3625 if (__d1 == 0 && __d2 == 0)
3631 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3634 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3637 auto __matches = std::__count_if(__first2, __last2,
3638 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3640 || std::__count_if(__scan, __last1,
3641 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3661 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3663 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3664 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3666 __glibcxx_requires_valid_range(__first1, __last1);
3667 __glibcxx_requires_valid_range(__first2, __last2);
3670 std::__is_permutation(__first1, __last1, __first2, __last2,
3671 __gnu_cxx::__ops::__iter_equal_to_iter());
3688 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3689 typename _BinaryPredicate>
3691 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3692 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3693 _BinaryPredicate __pred)
3695 __glibcxx_requires_valid_range(__first1, __last1);
3696 __glibcxx_requires_valid_range(__first2, __last2);
3698 return std::__is_permutation(__first1, __last1, __first2, __last2,
3699 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3702 #if __cplusplus > 201402L 3704 #define __cpp_lib_clamp 201603 3714 template<
typename _Tp>
3715 constexpr
const _Tp&
3716 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi)
3718 __glibcxx_assert(!(__hi < __lo));
3719 return (__val < __lo) ? __lo : (__hi < __val) ? __hi : __val;
3732 template<
typename _Tp,
typename _Compare>
3733 constexpr
const _Tp&
3734 clamp(
const _Tp& __val,
const _Tp& __lo,
const _Tp& __hi, _Compare __comp)
3736 __glibcxx_assert(!__comp(__hi, __lo));
3737 return __comp(__val, __lo) ? __lo : __comp(__hi, __val) ? __hi : __val;
3742 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 3764 template<
typename _IntType,
typename _UniformRandomBitGenerator>
3767 _UniformRandomBitGenerator&& __g)
3786 template<
typename _RandomAccessIterator,
3787 typename _UniformRandomNumberGenerator>
3789 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3790 _UniformRandomNumberGenerator&& __g)
3793 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3794 _RandomAccessIterator>)
3795 __glibcxx_requires_valid_range(__first, __last);
3797 if (__first == __last)
3800 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3803 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3805 typedef typename __distr_type::param_type __p_type;
3807 typedef typename remove_reference<_UniformRandomNumberGenerator>::type
3809 typedef typename common_type<typename _Gen::result_type, __ud_type>::type
3812 const __uc_type __urngrange = __g.
max() - __g.min();
3813 const __uc_type __urange = __uc_type(__last - __first);
3815 if (__urngrange / __urange >= __urange)
3818 _RandomAccessIterator __i = __first + 1;
3824 if ((__urange % 2) == 0)
3826 __distr_type __d{0, 1};
3834 while (__i != __last)
3836 const __uc_type __swap_range = __uc_type(__i - __first) + 1;
3850 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3851 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3857 _GLIBCXX_END_NAMESPACE_VERSION
3859 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3873 template<
typename _InputIterator,
typename _Function>
3875 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3878 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3879 __glibcxx_requires_valid_range(__first, __last);
3880 for (; __first != __last; ++__first)
3894 template<
typename _InputIterator,
typename _Tp>
3895 inline _InputIterator
3896 find(_InputIterator __first, _InputIterator __last,
3900 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3901 __glibcxx_function_requires(_EqualOpConcept<
3902 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3903 __glibcxx_requires_valid_range(__first, __last);
3905 __gnu_cxx::__ops::__iter_equals_val(__val));
3918 template<
typename _InputIterator,
typename _Predicate>
3919 inline _InputIterator
3920 find_if(_InputIterator __first, _InputIterator __last,
3924 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3925 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3926 typename iterator_traits<_InputIterator>::value_type>)
3927 __glibcxx_requires_valid_range(__first, __last);
3930 __gnu_cxx::__ops::__pred_iter(__pred));
3949 template<
typename _InputIterator,
typename _ForwardIterator>
3951 find_first_of(_InputIterator __first1, _InputIterator __last1,
3952 _ForwardIterator __first2, _ForwardIterator __last2)
3955 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3956 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3957 __glibcxx_function_requires(_EqualOpConcept<
3958 typename iterator_traits<_InputIterator>::value_type,
3959 typename iterator_traits<_ForwardIterator>::value_type>)
3960 __glibcxx_requires_valid_range(__first1, __last1);
3961 __glibcxx_requires_valid_range(__first2, __last2);
3963 for (; __first1 != __last1; ++__first1)
3964 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3965 if (*__first1 == *__iter)
3989 template<
typename _InputIterator,
typename _ForwardIterator,
3990 typename _BinaryPredicate>
3992 find_first_of(_InputIterator __first1, _InputIterator __last1,
3993 _ForwardIterator __first2, _ForwardIterator __last2,
3994 _BinaryPredicate __comp)
3997 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3998 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3999 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4000 typename iterator_traits<_InputIterator>::value_type,
4001 typename iterator_traits<_ForwardIterator>::value_type>)
4002 __glibcxx_requires_valid_range(__first1, __last1);
4003 __glibcxx_requires_valid_range(__first2, __last2);
4005 for (; __first1 != __last1; ++__first1)
4006 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4007 if (__comp(*__first1, *__iter))
4021 template<
typename _ForwardIterator>
4022 inline _ForwardIterator
4023 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4026 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4027 __glibcxx_function_requires(_EqualityComparableConcept<
4028 typename iterator_traits<_ForwardIterator>::value_type>)
4029 __glibcxx_requires_valid_range(__first, __last);
4031 return std::__adjacent_find(__first, __last,
4032 __gnu_cxx::__ops::__iter_equal_to_iter());
4046 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4047 inline _ForwardIterator
4048 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4049 _BinaryPredicate __binary_pred)
4052 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4053 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4054 typename iterator_traits<_ForwardIterator>::value_type,
4055 typename iterator_traits<_ForwardIterator>::value_type>)
4056 __glibcxx_requires_valid_range(__first, __last);
4058 return std::__adjacent_find(__first, __last,
4059 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
4071 template<
typename _InputIterator,
typename _Tp>
4072 inline typename iterator_traits<_InputIterator>::difference_type
4073 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4076 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4077 __glibcxx_function_requires(_EqualOpConcept<
4078 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4079 __glibcxx_requires_valid_range(__first, __last);
4081 return std::__count_if(__first, __last,
4082 __gnu_cxx::__ops::__iter_equals_val(__value));
4094 template<
typename _InputIterator,
typename _Predicate>
4095 inline typename iterator_traits<_InputIterator>::difference_type
4096 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4099 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4100 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4101 typename iterator_traits<_InputIterator>::value_type>)
4102 __glibcxx_requires_valid_range(__first, __last);
4104 return std::__count_if(__first, __last,
4105 __gnu_cxx::__ops::__pred_iter(__pred));
4134 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4135 inline _ForwardIterator1
4136 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4137 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4140 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4141 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4142 __glibcxx_function_requires(_EqualOpConcept<
4143 typename iterator_traits<_ForwardIterator1>::value_type,
4144 typename iterator_traits<_ForwardIterator2>::value_type>)
4145 __glibcxx_requires_valid_range(__first1, __last1);
4146 __glibcxx_requires_valid_range(__first2, __last2);
4148 return std::__search(__first1, __last1, __first2, __last2,
4149 __gnu_cxx::__ops::__iter_equal_to_iter());
4173 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4174 typename _BinaryPredicate>
4175 inline _ForwardIterator1
4176 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4177 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4178 _BinaryPredicate __predicate)
4181 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4182 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4183 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4184 typename iterator_traits<_ForwardIterator1>::value_type,
4185 typename iterator_traits<_ForwardIterator2>::value_type>)
4186 __glibcxx_requires_valid_range(__first1, __last1);
4187 __glibcxx_requires_valid_range(__first2, __last2);
4189 return std::__search(__first1, __last1, __first2, __last2,
4190 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4208 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4209 inline _ForwardIterator
4210 search_n(_ForwardIterator __first, _ForwardIterator __last,
4211 _Integer __count,
const _Tp& __val)
4214 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4215 __glibcxx_function_requires(_EqualOpConcept<
4216 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4217 __glibcxx_requires_valid_range(__first, __last);
4219 return std::__search_n(__first, __last, __count,
4220 __gnu_cxx::__ops::__iter_equals_val(__val));
4241 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4242 typename _BinaryPredicate>
4243 inline _ForwardIterator
4244 search_n(_ForwardIterator __first, _ForwardIterator __last,
4245 _Integer __count,
const _Tp& __val,
4246 _BinaryPredicate __binary_pred)
4249 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4250 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4251 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4252 __glibcxx_requires_valid_range(__first, __last);
4254 return std::__search_n(__first, __last, __count,
4255 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4275 template<
typename _InputIterator,
typename _OutputIterator,
4276 typename _UnaryOperation>
4278 transform(_InputIterator __first, _InputIterator __last,
4279 _OutputIterator __result, _UnaryOperation __unary_op)
4282 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4283 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4285 __typeof__(__unary_op(*__first))>)
4286 __glibcxx_requires_valid_range(__first, __last);
4288 for (; __first != __last; ++__first, (void)++__result)
4289 *__result = __unary_op(*__first);
4312 template<
typename _InputIterator1,
typename _InputIterator2,
4313 typename _OutputIterator,
typename _BinaryOperation>
4315 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4316 _InputIterator2 __first2, _OutputIterator __result,
4317 _BinaryOperation __binary_op)
4320 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4321 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4322 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4324 __typeof__(__binary_op(*__first1,*__first2))>)
4325 __glibcxx_requires_valid_range(__first1, __last1);
4327 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4328 *__result = __binary_op(*__first1, *__first2);
4345 template<
typename _ForwardIterator,
typename _Tp>
4347 replace(_ForwardIterator __first, _ForwardIterator __last,
4348 const _Tp& __old_value,
const _Tp& __new_value)
4351 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4353 __glibcxx_function_requires(_EqualOpConcept<
4354 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4355 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4356 typename iterator_traits<_ForwardIterator>::value_type>)
4357 __glibcxx_requires_valid_range(__first, __last);
4359 for (; __first != __last; ++__first)
4360 if (*__first == __old_value)
4361 *__first = __new_value;
4377 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4379 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4380 _Predicate __pred,
const _Tp& __new_value)
4383 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4385 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4386 typename iterator_traits<_ForwardIterator>::value_type>)
4387 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4388 typename iterator_traits<_ForwardIterator>::value_type>)
4389 __glibcxx_requires_valid_range(__first, __last);
4391 for (; __first != __last; ++__first)
4392 if (__pred(*__first))
4393 *__first = __new_value;
4409 template<
typename _ForwardIterator,
typename _Generator>
4411 generate(_ForwardIterator __first, _ForwardIterator __last,
4415 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4416 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4417 typename iterator_traits<_ForwardIterator>::value_type>)
4418 __glibcxx_requires_valid_range(__first, __last);
4420 for (; __first != __last; ++__first)
4440 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4442 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4445 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4447 __typeof__(__gen())>)
4449 for (__decltype(__n + 0) __niter = __n;
4450 __niter > 0; --__niter, ++__first)
4476 template<
typename _InputIterator,
typename _OutputIterator>
4477 inline _OutputIterator
4478 unique_copy(_InputIterator __first, _InputIterator __last,
4479 _OutputIterator __result)
4482 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4483 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4484 typename iterator_traits<_InputIterator>::value_type>)
4485 __glibcxx_function_requires(_EqualityComparableConcept<
4486 typename iterator_traits<_InputIterator>::value_type>)
4487 __glibcxx_requires_valid_range(__first, __last);
4489 if (__first == __last)
4492 __gnu_cxx::__ops::__iter_equal_to_iter(),
4516 template<
typename _InputIterator,
typename _OutputIterator,
4517 typename _BinaryPredicate>
4518 inline _OutputIterator
4519 unique_copy(_InputIterator __first, _InputIterator __last,
4520 _OutputIterator __result,
4521 _BinaryPredicate __binary_pred)
4524 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4525 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4526 typename iterator_traits<_InputIterator>::value_type>)
4527 __glibcxx_requires_valid_range(__first, __last);
4529 if (__first == __last)
4532 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4549 template<
typename _RandomAccessIterator>
4551 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4554 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4555 _RandomAccessIterator>)
4556 __glibcxx_requires_valid_range(__first, __last);
4558 if (__first != __last)
4559 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4562 _RandomAccessIterator __j = __first
4563 + std::rand() % ((__i - __first) + 1);
4584 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4586 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4587 #
if __cplusplus >= 201103L
4588 _RandomNumberGenerator&& __rand)
4590 _RandomNumberGenerator& __rand)
4594 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4595 _RandomAccessIterator>)
4596 __glibcxx_requires_valid_range(__first, __last);
4598 if (__first == __last)
4600 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4602 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4624 template<
typename _ForwardIterator,
typename _Predicate>
4625 inline _ForwardIterator
4626 partition(_ForwardIterator __first, _ForwardIterator __last,
4630 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4632 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4633 typename iterator_traits<_ForwardIterator>::value_type>)
4634 __glibcxx_requires_valid_range(__first, __last);
4657 template<
typename _RandomAccessIterator>
4659 partial_sort(_RandomAccessIterator __first,
4660 _RandomAccessIterator __middle,
4661 _RandomAccessIterator __last)
4664 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4665 _RandomAccessIterator>)
4666 __glibcxx_function_requires(_LessThanComparableConcept<
4667 typename iterator_traits<_RandomAccessIterator>::value_type>)
4668 __glibcxx_requires_valid_range(__first, __middle);
4669 __glibcxx_requires_valid_range(__middle, __last);
4670 __glibcxx_requires_irreflexive(__first, __last);
4672 std::__partial_sort(__first, __middle, __last,
4673 __gnu_cxx::__ops::__iter_less_iter());
4695 template<
typename _RandomAccessIterator,
typename _Compare>
4697 partial_sort(_RandomAccessIterator __first,
4698 _RandomAccessIterator __middle,
4699 _RandomAccessIterator __last,
4703 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4704 _RandomAccessIterator>)
4705 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4706 typename iterator_traits<_RandomAccessIterator>::value_type,
4707 typename iterator_traits<_RandomAccessIterator>::value_type>)
4708 __glibcxx_requires_valid_range(__first, __middle);
4709 __glibcxx_requires_valid_range(__middle, __last);
4710 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4712 std::__partial_sort(__first, __middle, __last,
4713 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4731 template<
typename _RandomAccessIterator>
4733 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4734 _RandomAccessIterator __last)
4737 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4738 _RandomAccessIterator>)
4739 __glibcxx_function_requires(_LessThanComparableConcept<
4740 typename iterator_traits<_RandomAccessIterator>::value_type>)
4741 __glibcxx_requires_valid_range(__first, __nth);
4742 __glibcxx_requires_valid_range(__nth, __last);
4743 __glibcxx_requires_irreflexive(__first, __last);
4745 if (__first == __last || __nth == __last)
4748 std::__introselect(__first, __nth, __last,
4750 __gnu_cxx::__ops::__iter_less_iter());
4770 template<
typename _RandomAccessIterator,
typename _Compare>
4772 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4773 _RandomAccessIterator __last, _Compare __comp)
4776 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4777 _RandomAccessIterator>)
4778 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4779 typename iterator_traits<_RandomAccessIterator>::value_type,
4780 typename iterator_traits<_RandomAccessIterator>::value_type>)
4781 __glibcxx_requires_valid_range(__first, __nth);
4782 __glibcxx_requires_valid_range(__nth, __last);
4783 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4785 if (__first == __last || __nth == __last)
4788 std::__introselect(__first, __nth, __last,
4790 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4807 template<
typename _RandomAccessIterator>
4809 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4812 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4813 _RandomAccessIterator>)
4814 __glibcxx_function_requires(_LessThanComparableConcept<
4815 typename iterator_traits<_RandomAccessIterator>::value_type>)
4816 __glibcxx_requires_valid_range(__first, __last);
4817 __glibcxx_requires_irreflexive(__first, __last);
4819 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4837 template<
typename _RandomAccessIterator,
typename _Compare>
4839 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4843 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4844 _RandomAccessIterator>)
4845 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4846 typename iterator_traits<_RandomAccessIterator>::value_type,
4847 typename iterator_traits<_RandomAccessIterator>::value_type>)
4848 __glibcxx_requires_valid_range(__first, __last);
4849 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4851 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4854 template<
typename _InputIterator1,
typename _InputIterator2,
4855 typename _OutputIterator,
typename _Compare>
4857 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4858 _InputIterator2 __first2, _InputIterator2 __last2,
4859 _OutputIterator __result, _Compare __comp)
4861 while (__first1 != __last1 && __first2 != __last2)
4863 if (__comp(__first2, __first1))
4865 *__result = *__first2;
4870 *__result = *__first1;
4875 return std::copy(__first2, __last2,
4876 std::copy(__first1, __last1, __result));
4898 template<
typename _InputIterator1,
typename _InputIterator2,
4899 typename _OutputIterator>
4900 inline _OutputIterator
4901 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4902 _InputIterator2 __first2, _InputIterator2 __last2,
4903 _OutputIterator __result)
4906 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4907 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4908 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4909 typename iterator_traits<_InputIterator1>::value_type>)
4910 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4911 typename iterator_traits<_InputIterator2>::value_type>)
4912 __glibcxx_function_requires(_LessThanOpConcept<
4913 typename iterator_traits<_InputIterator2>::value_type,
4914 typename iterator_traits<_InputIterator1>::value_type>)
4915 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4916 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4917 __glibcxx_requires_irreflexive2(__first1, __last1);
4918 __glibcxx_requires_irreflexive2(__first2, __last2);
4920 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4921 __first2, __last2, __result,
4922 __gnu_cxx::__ops::__iter_less_iter());
4948 template<
typename _InputIterator1,
typename _InputIterator2,
4949 typename _OutputIterator,
typename _Compare>
4950 inline _OutputIterator
4951 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4952 _InputIterator2 __first2, _InputIterator2 __last2,
4953 _OutputIterator __result, _Compare __comp)
4956 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4957 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4958 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4959 typename iterator_traits<_InputIterator1>::value_type>)
4960 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4961 typename iterator_traits<_InputIterator2>::value_type>)
4962 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4963 typename iterator_traits<_InputIterator2>::value_type,
4964 typename iterator_traits<_InputIterator1>::value_type>)
4965 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4966 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4967 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4968 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4970 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4971 __first2, __last2, __result,
4972 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4975 template<
typename _RandomAccessIterator,
typename _Compare>
4977 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4980 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4982 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4986 _TmpBuf __buf(__first, __last);
4988 if (__buf.begin() == 0)
4991 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4992 _DistanceType(__buf.size()), __comp);
5012 template<
typename _RandomAccessIterator>
5014 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5017 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5018 _RandomAccessIterator>)
5019 __glibcxx_function_requires(_LessThanComparableConcept<
5020 typename iterator_traits<_RandomAccessIterator>::value_type>)
5021 __glibcxx_requires_valid_range(__first, __last);
5022 __glibcxx_requires_irreflexive(__first, __last);
5024 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5025 __gnu_cxx::__ops::__iter_less_iter());
5046 template<
typename _RandomAccessIterator,
typename _Compare>
5048 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5052 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5053 _RandomAccessIterator>)
5054 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5055 typename iterator_traits<_RandomAccessIterator>::value_type,
5056 typename iterator_traits<_RandomAccessIterator>::value_type>)
5057 __glibcxx_requires_valid_range(__first, __last);
5058 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5060 _GLIBCXX_STD_A::__stable_sort(__first, __last,
5061 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5064 template<
typename _InputIterator1,
typename _InputIterator2,
5065 typename _OutputIterator,
5068 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5069 _InputIterator2 __first2, _InputIterator2 __last2,
5070 _OutputIterator __result, _Compare __comp)
5072 while (__first1 != __last1 && __first2 != __last2)
5074 if (__comp(__first1, __first2))
5076 *__result = *__first1;
5079 else if (__comp(__first2, __first1))
5081 *__result = *__first2;
5086 *__result = *__first1;
5092 return std::copy(__first2, __last2,
5093 std::copy(__first1, __last1, __result));
5114 template<
typename _InputIterator1,
typename _InputIterator2,
5115 typename _OutputIterator>
5116 inline _OutputIterator
5117 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5118 _InputIterator2 __first2, _InputIterator2 __last2,
5119 _OutputIterator __result)
5122 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5123 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5124 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5125 typename iterator_traits<_InputIterator1>::value_type>)
5126 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5127 typename iterator_traits<_InputIterator2>::value_type>)
5128 __glibcxx_function_requires(_LessThanOpConcept<
5129 typename iterator_traits<_InputIterator1>::value_type,
5130 typename iterator_traits<_InputIterator2>::value_type>)
5131 __glibcxx_function_requires(_LessThanOpConcept<
5132 typename iterator_traits<_InputIterator2>::value_type,
5133 typename iterator_traits<_InputIterator1>::value_type>)
5134 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5135 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5136 __glibcxx_requires_irreflexive2(__first1, __last1);
5137 __glibcxx_requires_irreflexive2(__first2, __last2);
5139 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5140 __first2, __last2, __result,
5141 __gnu_cxx::__ops::__iter_less_iter());
5163 template<
typename _InputIterator1,
typename _InputIterator2,
5164 typename _OutputIterator,
typename _Compare>
5165 inline _OutputIterator
5166 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5167 _InputIterator2 __first2, _InputIterator2 __last2,
5168 _OutputIterator __result, _Compare __comp)
5171 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5172 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5173 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5174 typename iterator_traits<_InputIterator1>::value_type>)
5175 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5176 typename iterator_traits<_InputIterator2>::value_type>)
5177 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5178 typename iterator_traits<_InputIterator1>::value_type,
5179 typename iterator_traits<_InputIterator2>::value_type>)
5180 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5181 typename iterator_traits<_InputIterator2>::value_type,
5182 typename iterator_traits<_InputIterator1>::value_type>)
5183 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5184 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5185 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5186 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5188 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5189 __first2, __last2, __result,
5190 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5193 template<
typename _InputIterator1,
typename _InputIterator2,
5194 typename _OutputIterator,
5197 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5198 _InputIterator2 __first2, _InputIterator2 __last2,
5199 _OutputIterator __result, _Compare __comp)
5201 while (__first1 != __last1 && __first2 != __last2)
5202 if (__comp(__first1, __first2))
5204 else if (__comp(__first2, __first1))
5208 *__result = *__first1;
5233 template<
typename _InputIterator1,
typename _InputIterator2,
5234 typename _OutputIterator>
5235 inline _OutputIterator
5236 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5237 _InputIterator2 __first2, _InputIterator2 __last2,
5238 _OutputIterator __result)
5241 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5242 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5243 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5244 typename iterator_traits<_InputIterator1>::value_type>)
5245 __glibcxx_function_requires(_LessThanOpConcept<
5246 typename iterator_traits<_InputIterator1>::value_type,
5247 typename iterator_traits<_InputIterator2>::value_type>)
5248 __glibcxx_function_requires(_LessThanOpConcept<
5249 typename iterator_traits<_InputIterator2>::value_type,
5250 typename iterator_traits<_InputIterator1>::value_type>)
5251 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5252 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5253 __glibcxx_requires_irreflexive2(__first1, __last1);
5254 __glibcxx_requires_irreflexive2(__first2, __last2);
5256 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5257 __first2, __last2, __result,
5258 __gnu_cxx::__ops::__iter_less_iter());
5281 template<
typename _InputIterator1,
typename _InputIterator2,
5282 typename _OutputIterator,
typename _Compare>
5283 inline _OutputIterator
5284 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5285 _InputIterator2 __first2, _InputIterator2 __last2,
5286 _OutputIterator __result, _Compare __comp)
5289 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5290 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5291 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5292 typename iterator_traits<_InputIterator1>::value_type>)
5293 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5294 typename iterator_traits<_InputIterator1>::value_type,
5295 typename iterator_traits<_InputIterator2>::value_type>)
5296 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5297 typename iterator_traits<_InputIterator2>::value_type,
5298 typename iterator_traits<_InputIterator1>::value_type>)
5299 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5300 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5301 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5302 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5304 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5305 __first2, __last2, __result,
5306 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5309 template<
typename _InputIterator1,
typename _InputIterator2,
5310 typename _OutputIterator,
5313 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5314 _InputIterator2 __first2, _InputIterator2 __last2,
5315 _OutputIterator __result, _Compare __comp)
5317 while (__first1 != __last1 && __first2 != __last2)
5318 if (__comp(__first1, __first2))
5320 *__result = *__first1;
5324 else if (__comp(__first2, __first1))
5331 return std::copy(__first1, __last1, __result);
5353 template<
typename _InputIterator1,
typename _InputIterator2,
5354 typename _OutputIterator>
5355 inline _OutputIterator
5356 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5357 _InputIterator2 __first2, _InputIterator2 __last2,
5358 _OutputIterator __result)
5361 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5362 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5363 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5364 typename iterator_traits<_InputIterator1>::value_type>)
5365 __glibcxx_function_requires(_LessThanOpConcept<
5366 typename iterator_traits<_InputIterator1>::value_type,
5367 typename iterator_traits<_InputIterator2>::value_type>)
5368 __glibcxx_function_requires(_LessThanOpConcept<
5369 typename iterator_traits<_InputIterator2>::value_type,
5370 typename iterator_traits<_InputIterator1>::value_type>)
5371 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5372 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5373 __glibcxx_requires_irreflexive2(__first1, __last1);
5374 __glibcxx_requires_irreflexive2(__first2, __last2);
5376 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5377 __first2, __last2, __result,
5378 __gnu_cxx::__ops::__iter_less_iter());
5403 template<
typename _InputIterator1,
typename _InputIterator2,
5404 typename _OutputIterator,
typename _Compare>
5405 inline _OutputIterator
5406 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5407 _InputIterator2 __first2, _InputIterator2 __last2,
5408 _OutputIterator __result, _Compare __comp)
5411 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5412 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5413 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5414 typename iterator_traits<_InputIterator1>::value_type>)
5415 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5416 typename iterator_traits<_InputIterator1>::value_type,
5417 typename iterator_traits<_InputIterator2>::value_type>)
5418 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5419 typename iterator_traits<_InputIterator2>::value_type,
5420 typename iterator_traits<_InputIterator1>::value_type>)
5421 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5422 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5423 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5424 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5426 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5427 __first2, __last2, __result,
5428 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5431 template<
typename _InputIterator1,
typename _InputIterator2,
5432 typename _OutputIterator,
5435 __set_symmetric_difference(_InputIterator1 __first1,
5436 _InputIterator1 __last1,
5437 _InputIterator2 __first2,
5438 _InputIterator2 __last2,
5439 _OutputIterator __result,
5442 while (__first1 != __last1 && __first2 != __last2)
5443 if (__comp(__first1, __first2))
5445 *__result = *__first1;
5449 else if (__comp(__first2, __first1))
5451 *__result = *__first2;
5460 return std::copy(__first2, __last2,
5461 std::copy(__first1, __last1, __result));
5481 template<
typename _InputIterator1,
typename _InputIterator2,
5482 typename _OutputIterator>
5483 inline _OutputIterator
5484 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5485 _InputIterator2 __first2, _InputIterator2 __last2,
5486 _OutputIterator __result)
5489 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5490 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5491 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5492 typename iterator_traits<_InputIterator1>::value_type>)
5493 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5494 typename iterator_traits<_InputIterator2>::value_type>)
5495 __glibcxx_function_requires(_LessThanOpConcept<
5496 typename iterator_traits<_InputIterator1>::value_type,
5497 typename iterator_traits<_InputIterator2>::value_type>)
5498 __glibcxx_function_requires(_LessThanOpConcept<
5499 typename iterator_traits<_InputIterator2>::value_type,
5500 typename iterator_traits<_InputIterator1>::value_type>)
5501 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5502 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5503 __glibcxx_requires_irreflexive2(__first1, __last1);
5504 __glibcxx_requires_irreflexive2(__first2, __last2);
5506 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5507 __first2, __last2, __result,
5508 __gnu_cxx::__ops::__iter_less_iter());
5531 template<
typename _InputIterator1,
typename _InputIterator2,
5532 typename _OutputIterator,
typename _Compare>
5533 inline _OutputIterator
5534 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5535 _InputIterator2 __first2, _InputIterator2 __last2,
5536 _OutputIterator __result,
5540 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5541 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5542 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5543 typename iterator_traits<_InputIterator1>::value_type>)
5544 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5545 typename iterator_traits<_InputIterator2>::value_type>)
5546 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5547 typename iterator_traits<_InputIterator1>::value_type,
5548 typename iterator_traits<_InputIterator2>::value_type>)
5549 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5550 typename iterator_traits<_InputIterator2>::value_type,
5551 typename iterator_traits<_InputIterator1>::value_type>)
5552 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5553 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5554 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5555 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5557 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5558 __first2, __last2, __result,
5559 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5562 template<
typename _ForwardIterator,
typename _Compare>
5563 _GLIBCXX14_CONSTEXPR
5565 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5568 if (__first == __last)
5570 _ForwardIterator __result = __first;
5571 while (++__first != __last)
5572 if (__comp(__first, __result))
5584 template<
typename _ForwardIterator>
5585 _GLIBCXX14_CONSTEXPR
5587 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5590 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5591 __glibcxx_function_requires(_LessThanComparableConcept<
5592 typename iterator_traits<_ForwardIterator>::value_type>)
5593 __glibcxx_requires_valid_range(__first, __last);
5594 __glibcxx_requires_irreflexive(__first, __last);
5596 return _GLIBCXX_STD_A::__min_element(__first, __last,
5597 __gnu_cxx::__ops::__iter_less_iter());
5609 template<
typename _ForwardIterator,
typename _Compare>
5610 _GLIBCXX14_CONSTEXPR
5611 inline _ForwardIterator
5612 min_element(_ForwardIterator __first, _ForwardIterator __last,
5616 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5617 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5618 typename iterator_traits<_ForwardIterator>::value_type,
5619 typename iterator_traits<_ForwardIterator>::value_type>)
5620 __glibcxx_requires_valid_range(__first, __last);
5621 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5623 return _GLIBCXX_STD_A::__min_element(__first, __last,
5624 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5627 template<
typename _ForwardIterator,
typename _Compare>
5628 _GLIBCXX14_CONSTEXPR
5630 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5633 if (__first == __last)
return __first;
5634 _ForwardIterator __result = __first;
5635 while (++__first != __last)
5636 if (__comp(__result, __first))
5648 template<
typename _ForwardIterator>
5649 _GLIBCXX14_CONSTEXPR
5650 inline _ForwardIterator
5651 max_element(_ForwardIterator __first, _ForwardIterator __last)
5654 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5655 __glibcxx_function_requires(_LessThanComparableConcept<
5656 typename iterator_traits<_ForwardIterator>::value_type>)
5657 __glibcxx_requires_valid_range(__first, __last);
5658 __glibcxx_requires_irreflexive(__first, __last);
5660 return _GLIBCXX_STD_A::__max_element(__first, __last,
5661 __gnu_cxx::__ops::__iter_less_iter());
5673 template<
typename _ForwardIterator,
typename _Compare>
5674 _GLIBCXX14_CONSTEXPR
5675 inline _ForwardIterator
5676 max_element(_ForwardIterator __first, _ForwardIterator __last,
5680 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5681 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5682 typename iterator_traits<_ForwardIterator>::value_type,
5683 typename iterator_traits<_ForwardIterator>::value_type>)
5684 __glibcxx_requires_valid_range(__first, __last);
5685 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5687 return _GLIBCXX_STD_A::__max_element(__first, __last,
5688 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5691 #if __cplusplus >= 201402L 5693 template<
typename _InputIterator,
typename _RandomAccessIterator,
5694 typename _Size,
typename _UniformRandomBitGenerator>
5695 _RandomAccessIterator
5698 _Size __n, _UniformRandomBitGenerator&& __g)
5701 using __param_type =
typename __distrib_type::param_type;
5702 __distrib_type __d{};
5703 _Size __sample_sz = 0;
5704 while (__first != __last && __sample_sz != __n)
5706 __out[__sample_sz++] = *__first;
5709 for (
auto __pop_sz = __sample_sz; __first != __last;
5710 ++__first, (void) ++__pop_sz)
5712 const auto __k = __d(__g, __param_type{0, __pop_sz});
5714 __out[__k] = *__first;
5716 return __out + __sample_sz;
5720 template<
typename _ForwardIterator,
typename _OutputIterator,
typename _Cat,
5721 typename _Size,
typename _UniformRandomBitGenerator>
5723 __sample(_ForwardIterator __first, _ForwardIterator __last,
5725 _OutputIterator __out, _Cat,
5726 _Size __n, _UniformRandomBitGenerator&& __g)
5729 using __param_type =
typename __distrib_type::param_type;
5730 using _USize = make_unsigned_t<_Size>;
5731 using _Gen = remove_reference_t<_UniformRandomBitGenerator>;
5732 using __uc_type = common_type_t<typename _Gen::result_type, _USize>;
5734 __distrib_type __d{};
5736 __n =
std::min(__n, __unsampled_sz);
5741 const __uc_type __urngrange = __g.max() - __g.min();
5742 if (__urngrange / __uc_type(__unsampled_sz) >= __uc_type(__unsampled_sz))
5746 while (__n != 0 && __unsampled_sz >= 2)
5754 *__out++ = *__first;
5760 if (__n == 0)
break;
5765 *__out++ = *__first;
5775 for (; __n != 0; ++__first)
5776 if (__d(__g, __param_type{0, --__unsampled_sz}) < __n)
5778 *__out++ = *__first;
5784 #if __cplusplus > 201402L 5785 #define __cpp_lib_sample 201603 5787 template<
typename _PopulationIterator,
typename _SampleIterator,
5788 typename _Distance,
typename _UniformRandomBitGenerator>
5790 sample(_PopulationIterator __first, _PopulationIterator __last,
5791 _SampleIterator __out, _Distance __n,
5792 _UniformRandomBitGenerator&& __g)
5794 using __pop_cat =
typename 5795 std::iterator_traits<_PopulationIterator>::iterator_category;
5796 using __samp_cat =
typename 5797 std::iterator_traits<_SampleIterator>::iterator_category;
5800 __or_<is_convertible<__pop_cat, forward_iterator_tag>,
5801 is_convertible<__samp_cat, random_access_iterator_tag>>::value,
5802 "output range must use a RandomAccessIterator when input range" 5803 " does not meet the ForwardIterator requirements");
5806 "sample size must be an integer type");
5808 typename iterator_traits<_PopulationIterator>::difference_type __d = __n;
5809 return std::__sample(__first, __last, __pop_cat{}, __out, __samp_cat{},
5810 __d, std::forward<_UniformRandomBitGenerator>(__g));
5815 _GLIBCXX_END_NAMESPACE_ALGO
_GLIBCXX14_CONSTEXPR _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
_T2 second
first is a copy of the first object
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
size_type requested_size() const
Returns the size requested by the constructor; may be >size().
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
_GLIBCXX14_CONSTEXPR pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
_RandomAccessIterator __sample(_InputIterator __first, _InputIterator __last, input_iterator_tag, _RandomAccessIterator __out, random_access_iterator_tag, _Size __n, _UniformRandomBitGenerator &&__g)
Reservoir sampling algorithm.
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
ISO C++ entities toplevel namespace is std.
bool none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for all the elements of a sequence.
size_type size() const
As per Table mumble.
_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...
_GLIBCXX14_CONSTEXPR _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
Marking output iterators.
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
_GLIBCXX17_CONSTEXPR iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
void __merge_without_buffer(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Compare __comp)
This is a helper function for the merge routines.
constexpr pair< typename __decay_and_strip< _T1 >::__type, typename __decay_and_strip< _T2 >::__type > make_pair(_T1 &&__x, _T2 &&__y)
A convenience wrapper for creating a pair from two objects.
_GLIBCXX14_CONSTEXPR pair< _ForwardIterator, _ForwardIterator > minmax_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return a pair of iterators pointing to the minimum and maximum elements in a range.
_InputIterator __find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred, input_iterator_tag)
This is an overload used by find algos for the Input Iterator case.
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.
_OutputIterator __move_merge(_InputIterator __first1, _InputIterator __last1, _InputIterator __first2, _InputIterator __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_sort_loop routines.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
_ForwardIterator __stable_partition_adaptive(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pointer __buffer, _Distance __buffer_size)
This is a helper function... Requires __first != __last and !__pred(__first) and __len == distance(__...
void __move_median_to_first(_Iterator __result, _Iterator __a, _Iterator __b, _Iterator __c, _Compare __comp)
Swaps the median value of *__a, *__b and *__c under __comp to *__result.
Bidirectional iterators support a superset of forward iterator operations.
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
_OutputIterator __unique_copy(_ForwardIterator __first, _ForwardIterator __last, _OutputIterator __result, _BinaryPredicate __binary_pred, forward_iterator_tag, output_iterator_tag)
void __insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
void __move_merge_adaptive_backward(_BidirectionalIterator1 __first1, _BidirectionalIterator1 __last1, _BidirectionalIterator2 __first2, _BidirectionalIterator2 __last2, _BidirectionalIterator3 __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
void __move_merge_adaptive(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp)
This is a helper function for the __merge_adaptive routines.
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
Struct holding two objects of arbitrary type.
_GLIBCXX17_CONSTEXPR void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
_ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
pair< _IntType, _IntType > __gen_two_uniform_ints(_IntType __b0, _IntType __b1, _UniformRandomBitGenerator &&__g)
Generate two uniformly distributed integers using a single distribution invocation.
Forward iterators support a superset of input iterator operations.
Random-access iterators support a superset of bidirectional iterator operations.
_InputIterator find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is false.
iterator begin()
As per Table mumble.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
result_type max() const
Returns the inclusive upper bound of the distribution range.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
void __merge_adaptive(_BidirectionalIterator __first, _BidirectionalIterator __middle, _BidirectionalIterator __last, _Distance __len1, _Distance __len2, _Pointer __buffer, _Distance __buffer_size, _Compare __comp)
This is a helper function for the merge routines.
_ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
Rotate the elements of a sequence.
_T1 first
second_type is the second bound type
_ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines the end of a sorted sequence using comparison functor.
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.