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,
2029 __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
2031 return std::__lower_bound(__first, __last, __val,
2032 __gnu_cxx::__ops::__iter_comp_val(__comp));
2035 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2037 __upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2038 const _Tp& __val, _Compare __comp)
2040 typedef typename iterator_traits<_ForwardIterator>::difference_type
2047 _DistanceType __half = __len >> 1;
2048 _ForwardIterator __middle = __first;
2050 if (__comp(__val, __middle))
2056 __len = __len - __half - 1;
2073 template<
typename _ForwardIterator,
typename _Tp>
2074 inline _ForwardIterator
2075 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2079 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2080 __glibcxx_function_requires(_LessThanOpConcept<
2081 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2082 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2083 __glibcxx_requires_irreflexive2(__first, __last);
2085 return std::__upper_bound(__first, __last, __val,
2086 __gnu_cxx::__ops::__val_less_iter());
2104 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2105 inline _ForwardIterator
2106 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2107 const _Tp& __val, _Compare __comp)
2110 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2111 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2112 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2113 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2115 __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
2117 return std::__upper_bound(__first, __last, __val,
2118 __gnu_cxx::__ops::__val_comp_iter(__comp));
2121 template<
typename _ForwardIterator,
typename _Tp,
2122 typename _CompareItTp,
typename _CompareTpIt>
2124 __equal_range(_ForwardIterator __first, _ForwardIterator __last,
2126 _CompareItTp __comp_it_val, _CompareTpIt __comp_val_it)
2128 typedef typename iterator_traits<_ForwardIterator>::difference_type
2135 _DistanceType __half = __len >> 1;
2136 _ForwardIterator __middle = __first;
2138 if (__comp_it_val(__middle, __val))
2142 __len = __len - __half - 1;
2144 else if (__comp_val_it(__val, __middle))
2148 _ForwardIterator __left
2149 = std::__lower_bound(__first, __middle, __val, __comp_it_val);
2151 _ForwardIterator __right
2152 = std::__upper_bound(++__middle, __first, __val, __comp_val_it);
2176 template<
typename _ForwardIterator,
typename _Tp>
2178 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2182 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2183 __glibcxx_function_requires(_LessThanOpConcept<
2184 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2185 __glibcxx_function_requires(_LessThanOpConcept<
2186 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2187 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2188 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2189 __glibcxx_requires_irreflexive2(__first, __last);
2191 return std::__equal_range(__first, __last, __val,
2192 __gnu_cxx::__ops::__iter_less_val(),
2193 __gnu_cxx::__ops::__val_less_iter());
2213 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2215 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2216 const _Tp& __val, _Compare __comp)
2219 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2220 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2221 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
2222 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2223 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2224 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2226 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2228 __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
2230 return std::__equal_range(__first, __last, __val,
2231 __gnu_cxx::__ops::__iter_comp_val(__comp),
2232 __gnu_cxx::__ops::__val_comp_iter(__comp));
2247 template<
typename _ForwardIterator,
typename _Tp>
2249 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2253 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2254 __glibcxx_function_requires(_LessThanOpConcept<
2255 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2256 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2257 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2258 __glibcxx_requires_irreflexive2(__first, __last);
2260 _ForwardIterator __i
2261 = std::__lower_bound(__first, __last, __val,
2262 __gnu_cxx::__ops::__iter_less_val());
2263 return __i != __last && !(__val < *__i);
2281 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2283 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2284 const _Tp& __val, _Compare __comp)
2287 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2288 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2289 _Tp,
typename iterator_traits<_ForwardIterator>::value_type>)
2290 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2292 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2294 __glibcxx_requires_irreflexive_pred2(__first, __last, __comp);
2296 _ForwardIterator __i
2297 = std::__lower_bound(__first, __last, __val,
2298 __gnu_cxx::__ops::__iter_comp_val(__comp));
2299 return __i != __last && !bool(__comp(__val, *__i));
2305 template<
typename _InputIterator1,
typename _InputIterator2,
2306 typename _OutputIterator,
typename _Compare>
2309 _InputIterator2 __first2, _InputIterator2 __last2,
2310 _OutputIterator __result, _Compare __comp)
2312 while (__first1 != __last1 && __first2 != __last2)
2314 if (__comp(__first2, __first1))
2316 *__result = _GLIBCXX_MOVE(*__first2);
2321 *__result = _GLIBCXX_MOVE(*__first1);
2326 if (__first1 != __last1)
2327 _GLIBCXX_MOVE3(__first1, __last1, __result);
2331 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2332 typename _BidirectionalIterator3,
typename _Compare>
2335 _BidirectionalIterator1 __last1,
2336 _BidirectionalIterator2 __first2,
2337 _BidirectionalIterator2 __last2,
2338 _BidirectionalIterator3 __result,
2341 if (__first1 == __last1)
2343 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2346 else if (__first2 == __last2)
2353 if (__comp(__last2, __last1))
2355 *--__result = _GLIBCXX_MOVE(*__last1);
2356 if (__first1 == __last1)
2358 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2365 *--__result = _GLIBCXX_MOVE(*__last2);
2366 if (__first2 == __last2)
2374 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2376 _BidirectionalIterator1
2378 _BidirectionalIterator1 __middle,
2379 _BidirectionalIterator1 __last,
2380 _Distance __len1, _Distance __len2,
2381 _BidirectionalIterator2 __buffer,
2382 _Distance __buffer_size)
2384 _BidirectionalIterator2 __buffer_end;
2385 if (__len1 > __len2 && __len2 <= __buffer_size)
2389 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2390 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2391 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2396 else if (__len1 <= __buffer_size)
2400 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2401 _GLIBCXX_MOVE3(__middle, __last, __first);
2402 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2416 template<
typename _BidirectionalIterator,
typename _Distance,
2417 typename _Pointer,
typename _Compare>
2420 _BidirectionalIterator __middle,
2421 _BidirectionalIterator __last,
2422 _Distance __len1, _Distance __len2,
2423 _Pointer __buffer, _Distance __buffer_size,
2426 if (__len1 <= __len2 && __len1 <= __buffer_size)
2428 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2432 else if (__len2 <= __buffer_size)
2434 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2436 __buffer_end, __last, __comp);
2440 _BidirectionalIterator __first_cut = __first;
2441 _BidirectionalIterator __second_cut = __middle;
2442 _Distance __len11 = 0;
2443 _Distance __len22 = 0;
2444 if (__len1 > __len2)
2446 __len11 = __len1 / 2;
2449 = std::__lower_bound(__middle, __last, *__first_cut,
2450 __gnu_cxx::__ops::__iter_comp_val(__comp));
2455 __len22 = __len2 / 2;
2458 = std::__upper_bound(__first, __middle, *__second_cut,
2459 __gnu_cxx::__ops::__val_comp_iter(__comp));
2463 _BidirectionalIterator __new_middle
2465 __len1 - __len11, __len22, __buffer,
2468 __len22, __buffer, __buffer_size, __comp);
2471 __len2 - __len22, __buffer,
2472 __buffer_size, __comp);
2477 template<
typename _BidirectionalIterator,
typename _Distance,
2481 _BidirectionalIterator __middle,
2482 _BidirectionalIterator __last,
2483 _Distance __len1, _Distance __len2,
2486 if (__len1 == 0 || __len2 == 0)
2489 if (__len1 + __len2 == 2)
2491 if (__comp(__middle, __first))
2496 _BidirectionalIterator __first_cut = __first;
2497 _BidirectionalIterator __second_cut = __middle;
2498 _Distance __len11 = 0;
2499 _Distance __len22 = 0;
2500 if (__len1 > __len2)
2502 __len11 = __len1 / 2;
2505 = std::__lower_bound(__middle, __last, *__first_cut,
2506 __gnu_cxx::__ops::__iter_comp_val(__comp));
2511 __len22 = __len2 / 2;
2514 = std::__upper_bound(__first, __middle, *__second_cut,
2515 __gnu_cxx::__ops::__val_comp_iter(__comp));
2520 _BidirectionalIterator __new_middle = __first_cut;
2523 __len11, __len22, __comp);
2525 __len1 - __len11, __len2 - __len22, __comp);
2528 template<
typename _B
idirectionalIterator,
typename _Compare>
2530 __inplace_merge(_BidirectionalIterator __first,
2531 _BidirectionalIterator __middle,
2532 _BidirectionalIterator __last,
2535 typedef typename iterator_traits<_BidirectionalIterator>::value_type
2537 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
2540 if (__first == __middle || __middle == __last)
2543 const _DistanceType __len1 =
std::distance(__first, __middle);
2544 const _DistanceType __len2 =
std::distance(__middle, __last);
2547 _TmpBuf __buf(__first, __last);
2549 if (__buf.begin() == 0)
2551 (__first, __middle, __last, __len1, __len2, __comp);
2554 (__first, __middle, __last, __len1, __len2, __buf.begin(),
2555 _DistanceType(__buf.size()), __comp);
2576 template<
typename _B
idirectionalIterator>
2578 inplace_merge(_BidirectionalIterator __first,
2579 _BidirectionalIterator __middle,
2580 _BidirectionalIterator __last)
2583 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2584 _BidirectionalIterator>)
2585 __glibcxx_function_requires(_LessThanComparableConcept<
2586 typename iterator_traits<_BidirectionalIterator>::value_type>)
2587 __glibcxx_requires_sorted(__first, __middle);
2588 __glibcxx_requires_sorted(__middle, __last);
2589 __glibcxx_requires_irreflexive(__first, __last);
2591 std::__inplace_merge(__first, __middle, __last,
2592 __gnu_cxx::__ops::__iter_less_iter());
2617 template<
typename _B
idirectionalIterator,
typename _Compare>
2619 inplace_merge(_BidirectionalIterator __first,
2620 _BidirectionalIterator __middle,
2621 _BidirectionalIterator __last,
2625 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
2626 _BidirectionalIterator>)
2627 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2628 typename iterator_traits<_BidirectionalIterator>::value_type,
2629 typename iterator_traits<_BidirectionalIterator>::value_type>)
2630 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
2631 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
2632 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
2634 std::__inplace_merge(__first, __middle, __last,
2635 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2640 template<
typename _InputIterator,
typename _OutputIterator,
2644 _InputIterator __first2, _InputIterator __last2,
2645 _OutputIterator __result, _Compare __comp)
2647 while (__first1 != __last1 && __first2 != __last2)
2649 if (__comp(__first2, __first1))
2651 *__result = _GLIBCXX_MOVE(*__first2);
2656 *__result = _GLIBCXX_MOVE(*__first1);
2661 return _GLIBCXX_MOVE3(__first2, __last2,
2662 _GLIBCXX_MOVE3(__first1, __last1,
2666 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
2667 typename _Distance,
typename _Compare>
2669 __merge_sort_loop(_RandomAccessIterator1 __first,
2670 _RandomAccessIterator1 __last,
2671 _RandomAccessIterator2 __result, _Distance __step_size,
2674 const _Distance __two_step = 2 * __step_size;
2676 while (__last - __first >= __two_step)
2679 __first + __step_size,
2680 __first + __two_step,
2682 __first += __two_step;
2684 __step_size =
std::min(_Distance(__last - __first), __step_size);
2687 __first + __step_size, __last, __result, __comp);
2690 template<
typename _RandomAccessIterator,
typename _Distance,
2693 __chunk_insertion_sort(_RandomAccessIterator __first,
2694 _RandomAccessIterator __last,
2695 _Distance __chunk_size, _Compare __comp)
2697 while (__last - __first >= __chunk_size)
2700 __first += __chunk_size;
2705 enum { _S_chunk_size = 7 };
2707 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
2709 __merge_sort_with_buffer(_RandomAccessIterator __first,
2710 _RandomAccessIterator __last,
2711 _Pointer __buffer, _Compare __comp)
2713 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2716 const _Distance __len = __last - __first;
2717 const _Pointer __buffer_last = __buffer + __len;
2719 _Distance __step_size = _S_chunk_size;
2720 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
2722 while (__step_size < __len)
2724 std::__merge_sort_loop(__first, __last, __buffer,
2725 __step_size, __comp);
2727 std::__merge_sort_loop(__buffer, __buffer_last, __first,
2728 __step_size, __comp);
2733 template<
typename _RandomAccessIterator,
typename _Pointer,
2734 typename _Distance,
typename _Compare>
2736 __stable_sort_adaptive(_RandomAccessIterator __first,
2737 _RandomAccessIterator __last,
2738 _Pointer __buffer, _Distance __buffer_size,
2741 const _Distance __len = (__last - __first + 1) / 2;
2742 const _RandomAccessIterator __middle = __first + __len;
2743 if (__len > __buffer_size)
2745 std::__stable_sort_adaptive(__first, __middle, __buffer,
2746 __buffer_size, __comp);
2747 std::__stable_sort_adaptive(__middle, __last, __buffer,
2748 __buffer_size, __comp);
2752 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
2753 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
2756 _Distance(__middle - __first),
2757 _Distance(__last - __middle),
2758 __buffer, __buffer_size,
2763 template<
typename _RandomAccessIterator,
typename _Compare>
2766 _RandomAccessIterator __last, _Compare __comp)
2768 if (__last - __first < 15)
2773 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
2789 template<
typename _InputIterator1,
typename _InputIterator2,
2792 __includes(_InputIterator1 __first1, _InputIterator1 __last1,
2793 _InputIterator2 __first2, _InputIterator2 __last2,
2796 while (__first1 != __last1 && __first2 != __last2)
2797 if (__comp(__first2, __first1))
2799 else if (__comp(__first1, __first2))
2807 return __first2 == __last2;
2828 template<
typename _InputIterator1,
typename _InputIterator2>
2830 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2831 _InputIterator2 __first2, _InputIterator2 __last2)
2834 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2835 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2836 __glibcxx_function_requires(_LessThanOpConcept<
2837 typename iterator_traits<_InputIterator1>::value_type,
2838 typename iterator_traits<_InputIterator2>::value_type>)
2839 __glibcxx_function_requires(_LessThanOpConcept<
2840 typename iterator_traits<_InputIterator2>::value_type,
2841 typename iterator_traits<_InputIterator1>::value_type>)
2842 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
2843 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
2844 __glibcxx_requires_irreflexive2(__first1, __last1);
2845 __glibcxx_requires_irreflexive2(__first2, __last2);
2847 return std::__includes(__first1, __last1, __first2, __last2,
2848 __gnu_cxx::__ops::__iter_less_iter());
2872 template<
typename _InputIterator1,
typename _InputIterator2,
2875 includes(_InputIterator1 __first1, _InputIterator1 __last1,
2876 _InputIterator2 __first2, _InputIterator2 __last2,
2880 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
2881 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
2882 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2883 typename iterator_traits<_InputIterator1>::value_type,
2884 typename iterator_traits<_InputIterator2>::value_type>)
2885 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2886 typename iterator_traits<_InputIterator2>::value_type,
2887 typename iterator_traits<_InputIterator1>::value_type>)
2888 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
2889 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
2890 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
2891 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
2893 return std::__includes(__first1, __last1, __first2, __last2,
2894 __gnu_cxx::__ops::__iter_comp_iter(__comp));
2907 template<
typename _B
idirectionalIterator,
typename _Compare>
2909 __next_permutation(_BidirectionalIterator __first,
2910 _BidirectionalIterator __last, _Compare __comp)
2912 if (__first == __last)
2914 _BidirectionalIterator __i = __first;
2923 _BidirectionalIterator __ii = __i;
2925 if (__comp(__i, __ii))
2927 _BidirectionalIterator __j = __last;
2928 while (!__comp(__i, --__j))
2956 template<
typename _B
idirectionalIterator>
2958 next_permutation(_BidirectionalIterator __first,
2959 _BidirectionalIterator __last)
2962 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2963 _BidirectionalIterator>)
2964 __glibcxx_function_requires(_LessThanComparableConcept<
2965 typename iterator_traits<_BidirectionalIterator>::value_type>)
2966 __glibcxx_requires_valid_range(__first, __last);
2967 __glibcxx_requires_irreflexive(__first, __last);
2969 return std::__next_permutation
2970 (__first, __last, __gnu_cxx::__ops::__iter_less_iter());
2988 template<
typename _B
idirectionalIterator,
typename _Compare>
2990 next_permutation(_BidirectionalIterator __first,
2991 _BidirectionalIterator __last, _Compare __comp)
2994 __glibcxx_function_requires(_BidirectionalIteratorConcept<
2995 _BidirectionalIterator>)
2996 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2997 typename iterator_traits<_BidirectionalIterator>::value_type,
2998 typename iterator_traits<_BidirectionalIterator>::value_type>)
2999 __glibcxx_requires_valid_range(__first, __last);
3000 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3002 return std::__next_permutation
3003 (__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
3006 template<
typename _B
idirectionalIterator,
typename _Compare>
3008 __prev_permutation(_BidirectionalIterator __first,
3009 _BidirectionalIterator __last, _Compare __comp)
3011 if (__first == __last)
3013 _BidirectionalIterator __i = __first;
3022 _BidirectionalIterator __ii = __i;
3024 if (__comp(__ii, __i))
3026 _BidirectionalIterator __j = __last;
3027 while (!__comp(--__j, __i))
3056 template<
typename _B
idirectionalIterator>
3058 prev_permutation(_BidirectionalIterator __first,
3059 _BidirectionalIterator __last)
3062 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3063 _BidirectionalIterator>)
3064 __glibcxx_function_requires(_LessThanComparableConcept<
3065 typename iterator_traits<_BidirectionalIterator>::value_type>)
3066 __glibcxx_requires_valid_range(__first, __last);
3067 __glibcxx_requires_irreflexive(__first, __last);
3069 return std::__prev_permutation(__first, __last,
3070 __gnu_cxx::__ops::__iter_less_iter());
3088 template<
typename _B
idirectionalIterator,
typename _Compare>
3090 prev_permutation(_BidirectionalIterator __first,
3091 _BidirectionalIterator __last, _Compare __comp)
3094 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3095 _BidirectionalIterator>)
3096 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3097 typename iterator_traits<_BidirectionalIterator>::value_type,
3098 typename iterator_traits<_BidirectionalIterator>::value_type>)
3099 __glibcxx_requires_valid_range(__first, __last);
3100 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3102 return std::__prev_permutation(__first, __last,
3103 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3109 template<
typename _InputIterator,
typename _OutputIterator,
3110 typename _Predicate,
typename _Tp>
3112 __replace_copy_if(_InputIterator __first, _InputIterator __last,
3113 _OutputIterator __result,
3114 _Predicate __pred,
const _Tp& __new_value)
3116 for (; __first != __last; ++__first, (void)++__result)
3117 if (__pred(__first))
3118 *__result = __new_value;
3120 *__result = *__first;
3138 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3139 inline _OutputIterator
3140 replace_copy(_InputIterator __first, _InputIterator __last,
3141 _OutputIterator __result,
3142 const _Tp& __old_value,
const _Tp& __new_value)
3145 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3146 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3147 typename iterator_traits<_InputIterator>::value_type>)
3148 __glibcxx_function_requires(_EqualOpConcept<
3149 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3150 __glibcxx_requires_valid_range(__first, __last);
3152 return std::__replace_copy_if(__first, __last, __result,
3153 __gnu_cxx::__ops::__iter_equals_val(__old_value),
3172 template<
typename _InputIterator,
typename _OutputIterator,
3173 typename _Predicate,
typename _Tp>
3174 inline _OutputIterator
3175 replace_copy_if(_InputIterator __first, _InputIterator __last,
3176 _OutputIterator __result,
3177 _Predicate __pred,
const _Tp& __new_value)
3180 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3181 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3182 typename iterator_traits<_InputIterator>::value_type>)
3183 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3184 typename iterator_traits<_InputIterator>::value_type>)
3185 __glibcxx_requires_valid_range(__first, __last);
3187 return std::__replace_copy_if(__first, __last, __result,
3188 __gnu_cxx::__ops::__pred_iter(__pred),
3192 template<
typename _InputIterator,
typename _Predicate>
3193 typename iterator_traits<_InputIterator>::difference_type
3194 __count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3196 typename iterator_traits<_InputIterator>::difference_type __n = 0;
3197 for (; __first != __last; ++__first)
3198 if (__pred(__first))
3203 #if __cplusplus >= 201103L 3211 template<
typename _ForwardIterator>
3213 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3225 template<
typename _ForwardIterator,
typename _Compare>
3227 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3231 template<
typename _ForwardIterator,
typename _Compare>
3233 __is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3236 if (__first == __last)
3239 _ForwardIterator __next = __first;
3240 for (++__next; __next != __last; __first = __next, (void)++__next)
3241 if (__comp(__next, __first))
3254 template<
typename _ForwardIterator>
3255 inline _ForwardIterator
3256 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3259 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3260 __glibcxx_function_requires(_LessThanComparableConcept<
3261 typename iterator_traits<_ForwardIterator>::value_type>)
3262 __glibcxx_requires_valid_range(__first, __last);
3263 __glibcxx_requires_irreflexive(__first, __last);
3265 return std::__is_sorted_until(__first, __last,
3266 __gnu_cxx::__ops::__iter_less_iter());
3278 template<
typename _ForwardIterator,
typename _Compare>
3279 inline _ForwardIterator
3280 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3284 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3285 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3286 typename iterator_traits<_ForwardIterator>::value_type,
3287 typename iterator_traits<_ForwardIterator>::value_type>)
3288 __glibcxx_requires_valid_range(__first, __last);
3289 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3291 return std::__is_sorted_until(__first, __last,
3292 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3303 template<
typename _Tp>
3304 _GLIBCXX14_CONSTEXPR
3309 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
3311 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
3324 template<
typename _Tp,
typename _Compare>
3325 _GLIBCXX14_CONSTEXPR
3327 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
3333 template<
typename _ForwardIterator,
typename _Compare>
3334 _GLIBCXX14_CONSTEXPR
3336 __minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3339 _ForwardIterator __next = __first;
3340 if (__first == __last
3341 || ++__next == __last)
3344 _ForwardIterator __min{}, __max{};
3345 if (__comp(__next, __first))
3359 while (__first != __last)
3362 if (++__next == __last)
3364 if (__comp(__first, __min))
3366 else if (!__comp(__first, __max))
3371 if (__comp(__next, __first))
3373 if (__comp(__next, __min))
3375 if (!__comp(__first, __max))
3380 if (__comp(__first, __min))
3382 if (!__comp(__next, __max))
3404 template<
typename _ForwardIterator>
3405 _GLIBCXX14_CONSTEXPR
3407 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
3410 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3411 __glibcxx_function_requires(_LessThanComparableConcept<
3412 typename iterator_traits<_ForwardIterator>::value_type>)
3413 __glibcxx_requires_valid_range(__first, __last);
3414 __glibcxx_requires_irreflexive(__first, __last);
3416 return std::__minmax_element(__first, __last,
3417 __gnu_cxx::__ops::__iter_less_iter());
3432 template<
typename _ForwardIterator,
typename _Compare>
3433 _GLIBCXX14_CONSTEXPR
3435 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
3439 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3440 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3441 typename iterator_traits<_ForwardIterator>::value_type,
3442 typename iterator_traits<_ForwardIterator>::value_type>)
3443 __glibcxx_requires_valid_range(__first, __last);
3444 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
3446 return std::__minmax_element(__first, __last,
3447 __gnu_cxx::__ops::__iter_comp_iter(__comp));
3451 template<
typename _Tp>
3452 _GLIBCXX14_CONSTEXPR
3457 template<
typename _Tp,
typename _Compare>
3458 _GLIBCXX14_CONSTEXPR
3463 template<
typename _Tp>
3464 _GLIBCXX14_CONSTEXPR
3469 template<
typename _Tp,
typename _Compare>
3470 _GLIBCXX14_CONSTEXPR
3475 template<
typename _Tp>
3476 _GLIBCXX14_CONSTEXPR
3485 template<
typename _Tp,
typename _Compare>
3486 _GLIBCXX14_CONSTEXPR
3495 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3496 typename _BinaryPredicate>
3498 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3499 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3503 for (; __first1 != __last1; ++__first1, (void)++__first2)
3504 if (!__pred(__first1, __first2))
3507 if (__first1 == __last1)
3512 _ForwardIterator2 __last2 = __first2;
3514 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3517 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3521 = std::__count_if(__first2, __last2,
3522 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3523 if (0 == __matches ||
3524 std::__count_if(__scan, __last1,
3525 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3544 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3546 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3547 _ForwardIterator2 __first2)
3550 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3551 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3552 __glibcxx_function_requires(_EqualOpConcept<
3553 typename iterator_traits<_ForwardIterator1>::value_type,
3554 typename iterator_traits<_ForwardIterator2>::value_type>)
3555 __glibcxx_requires_valid_range(__first1, __last1);
3557 return std::__is_permutation(__first1, __last1, __first2,
3558 __gnu_cxx::__ops::__iter_equal_to_iter());
3575 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3576 typename _BinaryPredicate>
3578 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3579 _ForwardIterator2 __first2, _BinaryPredicate __pred)
3582 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
3583 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
3584 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3585 typename iterator_traits<_ForwardIterator1>::value_type,
3586 typename iterator_traits<_ForwardIterator2>::value_type>)
3587 __glibcxx_requires_valid_range(__first1, __last1);
3589 return std::__is_permutation(__first1, __last1, __first2,
3590 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3593 #if __cplusplus > 201103L 3594 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3595 typename _BinaryPredicate>
3597 __is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3598 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3599 _BinaryPredicate __pred)
3602 =
typename iterator_traits<_ForwardIterator1>::iterator_category;
3604 =
typename iterator_traits<_ForwardIterator2>::iterator_category;
3605 using _It1_is_RA = is_same<_Cat1, random_access_iterator_tag>;
3606 using _It2_is_RA = is_same<_Cat2, random_access_iterator_tag>;
3607 constexpr
bool __ra_iters = _It1_is_RA() && _It2_is_RA();
3618 for (; __first1 != __last1 && __first2 != __last2;
3619 ++__first1, (void)++__first2)
3620 if (!__pred(__first1, __first2))
3625 if (__first1 == __last1)
3632 if (__d1 == 0 && __d2 == 0)
3638 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
3641 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
3644 auto __matches = std::__count_if(__first2, __last2,
3645 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
3647 || std::__count_if(__scan, __last1,
3648 __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
3668 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
3670 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3671 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
3673 __glibcxx_requires_valid_range(__first1, __last1);
3674 __glibcxx_requires_valid_range(__first2, __last2);
3677 std::__is_permutation(__first1, __last1, __first2, __last2,
3678 __gnu_cxx::__ops::__iter_equal_to_iter());
3695 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
3696 typename _BinaryPredicate>
3698 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
3699 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
3700 _BinaryPredicate __pred)
3702 __glibcxx_requires_valid_range(__first1, __last1);
3703 __glibcxx_requires_valid_range(__first2, __last2);
3705 return std::__is_permutation(__first1, __last1, __first2, __last2,
3706 __gnu_cxx::__ops::__iter_comp_iter(__pred));
3710 #ifdef _GLIBCXX_USE_C99_STDINT_TR1 3723 template<
typename _RandomAccessIterator,
3724 typename _UniformRandomNumberGenerator>
3726 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
3727 _UniformRandomNumberGenerator&& __g)
3730 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
3731 _RandomAccessIterator>)
3732 __glibcxx_requires_valid_range(__first, __last);
3734 if (__first == __last)
3737 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3740 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
3742 typedef typename __distr_type::param_type __p_type;
3745 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
3746 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
3752 _GLIBCXX_END_NAMESPACE_VERSION
3754 _GLIBCXX_BEGIN_NAMESPACE_ALGO
3768 template<
typename _InputIterator,
typename _Function>
3770 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
3773 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3774 __glibcxx_requires_valid_range(__first, __last);
3775 for (; __first != __last; ++__first)
3777 return _GLIBCXX_MOVE(__f);
3789 template<
typename _InputIterator,
typename _Tp>
3790 inline _InputIterator
3791 find(_InputIterator __first, _InputIterator __last,
3795 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3796 __glibcxx_function_requires(_EqualOpConcept<
3797 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3798 __glibcxx_requires_valid_range(__first, __last);
3800 __gnu_cxx::__ops::__iter_equals_val(__val));
3813 template<
typename _InputIterator,
typename _Predicate>
3814 inline _InputIterator
3815 find_if(_InputIterator __first, _InputIterator __last,
3819 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3820 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3821 typename iterator_traits<_InputIterator>::value_type>)
3822 __glibcxx_requires_valid_range(__first, __last);
3825 __gnu_cxx::__ops::__pred_iter(__pred));
3844 template<
typename _InputIterator,
typename _ForwardIterator>
3846 find_first_of(_InputIterator __first1, _InputIterator __last1,
3847 _ForwardIterator __first2, _ForwardIterator __last2)
3850 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3851 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3852 __glibcxx_function_requires(_EqualOpConcept<
3853 typename iterator_traits<_InputIterator>::value_type,
3854 typename iterator_traits<_ForwardIterator>::value_type>)
3855 __glibcxx_requires_valid_range(__first1, __last1);
3856 __glibcxx_requires_valid_range(__first2, __last2);
3858 for (; __first1 != __last1; ++__first1)
3859 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3860 if (*__first1 == *__iter)
3884 template<
typename _InputIterator,
typename _ForwardIterator,
3885 typename _BinaryPredicate>
3887 find_first_of(_InputIterator __first1, _InputIterator __last1,
3888 _ForwardIterator __first2, _ForwardIterator __last2,
3889 _BinaryPredicate __comp)
3892 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3893 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3894 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3895 typename iterator_traits<_InputIterator>::value_type,
3896 typename iterator_traits<_ForwardIterator>::value_type>)
3897 __glibcxx_requires_valid_range(__first1, __last1);
3898 __glibcxx_requires_valid_range(__first2, __last2);
3900 for (; __first1 != __last1; ++__first1)
3901 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
3902 if (__comp(*__first1, *__iter))
3916 template<
typename _ForwardIterator>
3917 inline _ForwardIterator
3918 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
3921 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3922 __glibcxx_function_requires(_EqualityComparableConcept<
3923 typename iterator_traits<_ForwardIterator>::value_type>)
3924 __glibcxx_requires_valid_range(__first, __last);
3926 return std::__adjacent_find(__first, __last,
3927 __gnu_cxx::__ops::__iter_equal_to_iter());
3941 template<
typename _ForwardIterator,
typename _BinaryPredicate>
3942 inline _ForwardIterator
3943 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
3944 _BinaryPredicate __binary_pred)
3947 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3948 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
3949 typename iterator_traits<_ForwardIterator>::value_type,
3950 typename iterator_traits<_ForwardIterator>::value_type>)
3951 __glibcxx_requires_valid_range(__first, __last);
3953 return std::__adjacent_find(__first, __last,
3954 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred));
3966 template<
typename _InputIterator,
typename _Tp>
3967 inline typename iterator_traits<_InputIterator>::difference_type
3968 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
3971 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3972 __glibcxx_function_requires(_EqualOpConcept<
3973 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3974 __glibcxx_requires_valid_range(__first, __last);
3976 return std::__count_if(__first, __last,
3977 __gnu_cxx::__ops::__iter_equals_val(__value));
3989 template<
typename _InputIterator,
typename _Predicate>
3990 inline typename iterator_traits<_InputIterator>::difference_type
3991 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
3994 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3995 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3996 typename iterator_traits<_InputIterator>::value_type>)
3997 __glibcxx_requires_valid_range(__first, __last);
3999 return std::__count_if(__first, __last,
4000 __gnu_cxx::__ops::__pred_iter(__pred));
4029 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4030 inline _ForwardIterator1
4031 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4032 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4035 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4036 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4037 __glibcxx_function_requires(_EqualOpConcept<
4038 typename iterator_traits<_ForwardIterator1>::value_type,
4039 typename iterator_traits<_ForwardIterator2>::value_type>)
4040 __glibcxx_requires_valid_range(__first1, __last1);
4041 __glibcxx_requires_valid_range(__first2, __last2);
4043 return std::__search(__first1, __last1, __first2, __last2,
4044 __gnu_cxx::__ops::__iter_equal_to_iter());
4068 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4069 typename _BinaryPredicate>
4070 inline _ForwardIterator1
4071 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4072 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4073 _BinaryPredicate __predicate)
4076 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4077 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4078 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4079 typename iterator_traits<_ForwardIterator1>::value_type,
4080 typename iterator_traits<_ForwardIterator2>::value_type>)
4081 __glibcxx_requires_valid_range(__first1, __last1);
4082 __glibcxx_requires_valid_range(__first2, __last2);
4084 return std::__search(__first1, __last1, __first2, __last2,
4085 __gnu_cxx::__ops::__iter_comp_iter(__predicate));
4103 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4104 inline _ForwardIterator
4105 search_n(_ForwardIterator __first, _ForwardIterator __last,
4106 _Integer __count,
const _Tp& __val)
4109 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4110 __glibcxx_function_requires(_EqualOpConcept<
4111 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4112 __glibcxx_requires_valid_range(__first, __last);
4114 return std::__search_n(__first, __last, __count,
4115 __gnu_cxx::__ops::__iter_equals_val(__val));
4136 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4137 typename _BinaryPredicate>
4138 inline _ForwardIterator
4139 search_n(_ForwardIterator __first, _ForwardIterator __last,
4140 _Integer __count,
const _Tp& __val,
4141 _BinaryPredicate __binary_pred)
4144 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4145 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4146 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4147 __glibcxx_requires_valid_range(__first, __last);
4149 return std::__search_n(__first, __last, __count,
4150 __gnu_cxx::__ops::__iter_comp_val(__binary_pred, __val));
4170 template<
typename _InputIterator,
typename _OutputIterator,
4171 typename _UnaryOperation>
4173 transform(_InputIterator __first, _InputIterator __last,
4174 _OutputIterator __result, _UnaryOperation __unary_op)
4177 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4178 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4180 __typeof__(__unary_op(*__first))>)
4181 __glibcxx_requires_valid_range(__first, __last);
4183 for (; __first != __last; ++__first, (void)++__result)
4184 *__result = __unary_op(*__first);
4207 template<
typename _InputIterator1,
typename _InputIterator2,
4208 typename _OutputIterator,
typename _BinaryOperation>
4210 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4211 _InputIterator2 __first2, _OutputIterator __result,
4212 _BinaryOperation __binary_op)
4215 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4216 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4217 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4219 __typeof__(__binary_op(*__first1,*__first2))>)
4220 __glibcxx_requires_valid_range(__first1, __last1);
4222 for (; __first1 != __last1; ++__first1, (void)++__first2, ++__result)
4223 *__result = __binary_op(*__first1, *__first2);
4240 template<
typename _ForwardIterator,
typename _Tp>
4242 replace(_ForwardIterator __first, _ForwardIterator __last,
4243 const _Tp& __old_value,
const _Tp& __new_value)
4246 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4248 __glibcxx_function_requires(_EqualOpConcept<
4249 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4250 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4251 typename iterator_traits<_ForwardIterator>::value_type>)
4252 __glibcxx_requires_valid_range(__first, __last);
4254 for (; __first != __last; ++__first)
4255 if (*__first == __old_value)
4256 *__first = __new_value;
4272 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4274 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4275 _Predicate __pred,
const _Tp& __new_value)
4278 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4280 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4281 typename iterator_traits<_ForwardIterator>::value_type>)
4282 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4283 typename iterator_traits<_ForwardIterator>::value_type>)
4284 __glibcxx_requires_valid_range(__first, __last);
4286 for (; __first != __last; ++__first)
4287 if (__pred(*__first))
4288 *__first = __new_value;
4304 template<
typename _ForwardIterator,
typename _Generator>
4306 generate(_ForwardIterator __first, _ForwardIterator __last,
4310 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4311 __glibcxx_function_requires(_GeneratorConcept<_Generator,
4312 typename iterator_traits<_ForwardIterator>::value_type>)
4313 __glibcxx_requires_valid_range(__first, __last);
4315 for (; __first != __last; ++__first)
4335 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
4337 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
4340 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4342 __typeof__(__gen())>)
4344 for (__decltype(__n + 0) __niter = __n;
4345 __niter > 0; --__niter, ++__first)
4371 template<
typename _InputIterator,
typename _OutputIterator>
4372 inline _OutputIterator
4373 unique_copy(_InputIterator __first, _InputIterator __last,
4374 _OutputIterator __result)
4377 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4378 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4379 typename iterator_traits<_InputIterator>::value_type>)
4380 __glibcxx_function_requires(_EqualityComparableConcept<
4381 typename iterator_traits<_InputIterator>::value_type>)
4382 __glibcxx_requires_valid_range(__first, __last);
4384 if (__first == __last)
4387 __gnu_cxx::__ops::__iter_equal_to_iter(),
4411 template<
typename _InputIterator,
typename _OutputIterator,
4412 typename _BinaryPredicate>
4413 inline _OutputIterator
4414 unique_copy(_InputIterator __first, _InputIterator __last,
4415 _OutputIterator __result,
4416 _BinaryPredicate __binary_pred)
4419 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4420 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4421 typename iterator_traits<_InputIterator>::value_type>)
4422 __glibcxx_requires_valid_range(__first, __last);
4424 if (__first == __last)
4427 __gnu_cxx::__ops::__iter_comp_iter(__binary_pred),
4444 template<
typename _RandomAccessIterator>
4446 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
4449 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4450 _RandomAccessIterator>)
4451 __glibcxx_requires_valid_range(__first, __last);
4453 if (__first != __last)
4454 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4457 _RandomAccessIterator __j = __first
4458 + std::rand() % ((__i - __first) + 1);
4479 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
4481 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4482 #
if __cplusplus >= 201103L
4483 _RandomNumberGenerator&& __rand)
4485 _RandomNumberGenerator& __rand)
4489 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4490 _RandomAccessIterator>)
4491 __glibcxx_requires_valid_range(__first, __last);
4493 if (__first == __last)
4495 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4497 _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
4519 template<
typename _ForwardIterator,
typename _Predicate>
4520 inline _ForwardIterator
4521 partition(_ForwardIterator __first, _ForwardIterator __last,
4525 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4527 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4528 typename iterator_traits<_ForwardIterator>::value_type>)
4529 __glibcxx_requires_valid_range(__first, __last);
4552 template<
typename _RandomAccessIterator>
4554 partial_sort(_RandomAccessIterator __first,
4555 _RandomAccessIterator __middle,
4556 _RandomAccessIterator __last)
4559 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4560 _RandomAccessIterator>)
4561 __glibcxx_function_requires(_LessThanComparableConcept<
4562 typename iterator_traits<_RandomAccessIterator>::value_type>)
4563 __glibcxx_requires_valid_range(__first, __middle);
4564 __glibcxx_requires_valid_range(__middle, __last);
4565 __glibcxx_requires_irreflexive(__first, __last);
4567 std::__partial_sort(__first, __middle, __last,
4568 __gnu_cxx::__ops::__iter_less_iter());
4590 template<
typename _RandomAccessIterator,
typename _Compare>
4592 partial_sort(_RandomAccessIterator __first,
4593 _RandomAccessIterator __middle,
4594 _RandomAccessIterator __last,
4598 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4599 _RandomAccessIterator>)
4600 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4601 typename iterator_traits<_RandomAccessIterator>::value_type,
4602 typename iterator_traits<_RandomAccessIterator>::value_type>)
4603 __glibcxx_requires_valid_range(__first, __middle);
4604 __glibcxx_requires_valid_range(__middle, __last);
4605 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4607 std::__partial_sort(__first, __middle, __last,
4608 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4626 template<
typename _RandomAccessIterator>
4628 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4629 _RandomAccessIterator __last)
4632 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4633 _RandomAccessIterator>)
4634 __glibcxx_function_requires(_LessThanComparableConcept<
4635 typename iterator_traits<_RandomAccessIterator>::value_type>)
4636 __glibcxx_requires_valid_range(__first, __nth);
4637 __glibcxx_requires_valid_range(__nth, __last);
4638 __glibcxx_requires_irreflexive(__first, __last);
4640 if (__first == __last || __nth == __last)
4643 std::__introselect(__first, __nth, __last,
4645 __gnu_cxx::__ops::__iter_less_iter());
4665 template<
typename _RandomAccessIterator,
typename _Compare>
4667 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
4668 _RandomAccessIterator __last, _Compare __comp)
4671 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4672 _RandomAccessIterator>)
4673 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4674 typename iterator_traits<_RandomAccessIterator>::value_type,
4675 typename iterator_traits<_RandomAccessIterator>::value_type>)
4676 __glibcxx_requires_valid_range(__first, __nth);
4677 __glibcxx_requires_valid_range(__nth, __last);
4678 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4680 if (__first == __last || __nth == __last)
4683 std::__introselect(__first, __nth, __last,
4685 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4702 template<
typename _RandomAccessIterator>
4704 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4707 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4708 _RandomAccessIterator>)
4709 __glibcxx_function_requires(_LessThanComparableConcept<
4710 typename iterator_traits<_RandomAccessIterator>::value_type>)
4711 __glibcxx_requires_valid_range(__first, __last);
4712 __glibcxx_requires_irreflexive(__first, __last);
4714 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_less_iter());
4732 template<
typename _RandomAccessIterator,
typename _Compare>
4734 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4738 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4739 _RandomAccessIterator>)
4740 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4741 typename iterator_traits<_RandomAccessIterator>::value_type,
4742 typename iterator_traits<_RandomAccessIterator>::value_type>)
4743 __glibcxx_requires_valid_range(__first, __last);
4744 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4746 std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
4749 template<
typename _InputIterator1,
typename _InputIterator2,
4750 typename _OutputIterator,
typename _Compare>
4752 __merge(_InputIterator1 __first1, _InputIterator1 __last1,
4753 _InputIterator2 __first2, _InputIterator2 __last2,
4754 _OutputIterator __result, _Compare __comp)
4756 while (__first1 != __last1 && __first2 != __last2)
4758 if (__comp(__first2, __first1))
4760 *__result = *__first2;
4765 *__result = *__first1;
4770 return std::copy(__first2, __last2,
4771 std::copy(__first1, __last1, __result));
4793 template<
typename _InputIterator1,
typename _InputIterator2,
4794 typename _OutputIterator>
4795 inline _OutputIterator
4796 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4797 _InputIterator2 __first2, _InputIterator2 __last2,
4798 _OutputIterator __result)
4801 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4802 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4803 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4804 typename iterator_traits<_InputIterator1>::value_type>)
4805 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4806 typename iterator_traits<_InputIterator2>::value_type>)
4807 __glibcxx_function_requires(_LessThanOpConcept<
4808 typename iterator_traits<_InputIterator2>::value_type,
4809 typename iterator_traits<_InputIterator1>::value_type>)
4810 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
4811 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
4812 __glibcxx_requires_irreflexive2(__first1, __last1);
4813 __glibcxx_requires_irreflexive2(__first2, __last2);
4815 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4816 __first2, __last2, __result,
4817 __gnu_cxx::__ops::__iter_less_iter());
4843 template<
typename _InputIterator1,
typename _InputIterator2,
4844 typename _OutputIterator,
typename _Compare>
4845 inline _OutputIterator
4846 merge(_InputIterator1 __first1, _InputIterator1 __last1,
4847 _InputIterator2 __first2, _InputIterator2 __last2,
4848 _OutputIterator __result, _Compare __comp)
4851 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4852 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4853 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4854 typename iterator_traits<_InputIterator1>::value_type>)
4855 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4856 typename iterator_traits<_InputIterator2>::value_type>)
4857 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4858 typename iterator_traits<_InputIterator2>::value_type,
4859 typename iterator_traits<_InputIterator1>::value_type>)
4860 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
4861 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
4862 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
4863 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
4865 return _GLIBCXX_STD_A::__merge(__first1, __last1,
4866 __first2, __last2, __result,
4867 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4870 template<
typename _RandomAccessIterator,
typename _Compare>
4872 __stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4875 typedef typename iterator_traits<_RandomAccessIterator>::value_type
4877 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4881 _TmpBuf __buf(__first, __last);
4883 if (__buf.begin() == 0)
4886 std::__stable_sort_adaptive(__first, __last, __buf.begin(),
4887 _DistanceType(__buf.size()), __comp);
4907 template<
typename _RandomAccessIterator>
4909 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
4912 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4913 _RandomAccessIterator>)
4914 __glibcxx_function_requires(_LessThanComparableConcept<
4915 typename iterator_traits<_RandomAccessIterator>::value_type>)
4916 __glibcxx_requires_valid_range(__first, __last);
4917 __glibcxx_requires_irreflexive(__first, __last);
4919 _GLIBCXX_STD_A::__stable_sort(__first, __last,
4920 __gnu_cxx::__ops::__iter_less_iter());
4941 template<
typename _RandomAccessIterator,
typename _Compare>
4943 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
4947 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4948 _RandomAccessIterator>)
4949 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4950 typename iterator_traits<_RandomAccessIterator>::value_type,
4951 typename iterator_traits<_RandomAccessIterator>::value_type>)
4952 __glibcxx_requires_valid_range(__first, __last);
4953 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
4955 _GLIBCXX_STD_A::__stable_sort(__first, __last,
4956 __gnu_cxx::__ops::__iter_comp_iter(__comp));
4959 template<
typename _InputIterator1,
typename _InputIterator2,
4960 typename _OutputIterator,
4963 __set_union(_InputIterator1 __first1, _InputIterator1 __last1,
4964 _InputIterator2 __first2, _InputIterator2 __last2,
4965 _OutputIterator __result, _Compare __comp)
4967 while (__first1 != __last1 && __first2 != __last2)
4969 if (__comp(__first1, __first2))
4971 *__result = *__first1;
4974 else if (__comp(__first2, __first1))
4976 *__result = *__first2;
4981 *__result = *__first1;
4987 return std::copy(__first2, __last2,
4988 std::copy(__first1, __last1, __result));
5009 template<
typename _InputIterator1,
typename _InputIterator2,
5010 typename _OutputIterator>
5011 inline _OutputIterator
5012 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5013 _InputIterator2 __first2, _InputIterator2 __last2,
5014 _OutputIterator __result)
5017 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5018 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5019 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5020 typename iterator_traits<_InputIterator1>::value_type>)
5021 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5022 typename iterator_traits<_InputIterator2>::value_type>)
5023 __glibcxx_function_requires(_LessThanOpConcept<
5024 typename iterator_traits<_InputIterator1>::value_type,
5025 typename iterator_traits<_InputIterator2>::value_type>)
5026 __glibcxx_function_requires(_LessThanOpConcept<
5027 typename iterator_traits<_InputIterator2>::value_type,
5028 typename iterator_traits<_InputIterator1>::value_type>)
5029 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5030 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5031 __glibcxx_requires_irreflexive2(__first1, __last1);
5032 __glibcxx_requires_irreflexive2(__first2, __last2);
5034 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5035 __first2, __last2, __result,
5036 __gnu_cxx::__ops::__iter_less_iter());
5058 template<
typename _InputIterator1,
typename _InputIterator2,
5059 typename _OutputIterator,
typename _Compare>
5060 inline _OutputIterator
5061 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5062 _InputIterator2 __first2, _InputIterator2 __last2,
5063 _OutputIterator __result, _Compare __comp)
5066 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5067 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5068 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5069 typename iterator_traits<_InputIterator1>::value_type>)
5070 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5071 typename iterator_traits<_InputIterator2>::value_type>)
5072 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5073 typename iterator_traits<_InputIterator1>::value_type,
5074 typename iterator_traits<_InputIterator2>::value_type>)
5075 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5076 typename iterator_traits<_InputIterator2>::value_type,
5077 typename iterator_traits<_InputIterator1>::value_type>)
5078 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5079 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5080 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5081 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5083 return _GLIBCXX_STD_A::__set_union(__first1, __last1,
5084 __first2, __last2, __result,
5085 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5088 template<
typename _InputIterator1,
typename _InputIterator2,
5089 typename _OutputIterator,
5092 __set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5093 _InputIterator2 __first2, _InputIterator2 __last2,
5094 _OutputIterator __result, _Compare __comp)
5096 while (__first1 != __last1 && __first2 != __last2)
5097 if (__comp(__first1, __first2))
5099 else if (__comp(__first2, __first1))
5103 *__result = *__first1;
5128 template<
typename _InputIterator1,
typename _InputIterator2,
5129 typename _OutputIterator>
5130 inline _OutputIterator
5131 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5132 _InputIterator2 __first2, _InputIterator2 __last2,
5133 _OutputIterator __result)
5136 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5137 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5138 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5139 typename iterator_traits<_InputIterator1>::value_type>)
5140 __glibcxx_function_requires(_LessThanOpConcept<
5141 typename iterator_traits<_InputIterator1>::value_type,
5142 typename iterator_traits<_InputIterator2>::value_type>)
5143 __glibcxx_function_requires(_LessThanOpConcept<
5144 typename iterator_traits<_InputIterator2>::value_type,
5145 typename iterator_traits<_InputIterator1>::value_type>)
5146 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5147 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5148 __glibcxx_requires_irreflexive2(__first1, __last1);
5149 __glibcxx_requires_irreflexive2(__first2, __last2);
5151 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5152 __first2, __last2, __result,
5153 __gnu_cxx::__ops::__iter_less_iter());
5176 template<
typename _InputIterator1,
typename _InputIterator2,
5177 typename _OutputIterator,
typename _Compare>
5178 inline _OutputIterator
5179 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5180 _InputIterator2 __first2, _InputIterator2 __last2,
5181 _OutputIterator __result, _Compare __comp)
5184 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5185 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5186 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5187 typename iterator_traits<_InputIterator1>::value_type>)
5188 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5189 typename iterator_traits<_InputIterator1>::value_type,
5190 typename iterator_traits<_InputIterator2>::value_type>)
5191 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5192 typename iterator_traits<_InputIterator2>::value_type,
5193 typename iterator_traits<_InputIterator1>::value_type>)
5194 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5195 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5196 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5197 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5199 return _GLIBCXX_STD_A::__set_intersection(__first1, __last1,
5200 __first2, __last2, __result,
5201 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5204 template<
typename _InputIterator1,
typename _InputIterator2,
5205 typename _OutputIterator,
5208 __set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5209 _InputIterator2 __first2, _InputIterator2 __last2,
5210 _OutputIterator __result, _Compare __comp)
5212 while (__first1 != __last1 && __first2 != __last2)
5213 if (__comp(__first1, __first2))
5215 *__result = *__first1;
5219 else if (__comp(__first2, __first1))
5226 return std::copy(__first1, __last1, __result);
5248 template<
typename _InputIterator1,
typename _InputIterator2,
5249 typename _OutputIterator>
5250 inline _OutputIterator
5251 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5252 _InputIterator2 __first2, _InputIterator2 __last2,
5253 _OutputIterator __result)
5256 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5257 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5258 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5259 typename iterator_traits<_InputIterator1>::value_type>)
5260 __glibcxx_function_requires(_LessThanOpConcept<
5261 typename iterator_traits<_InputIterator1>::value_type,
5262 typename iterator_traits<_InputIterator2>::value_type>)
5263 __glibcxx_function_requires(_LessThanOpConcept<
5264 typename iterator_traits<_InputIterator2>::value_type,
5265 typename iterator_traits<_InputIterator1>::value_type>)
5266 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5267 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5268 __glibcxx_requires_irreflexive2(__first1, __last1);
5269 __glibcxx_requires_irreflexive2(__first2, __last2);
5271 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5272 __first2, __last2, __result,
5273 __gnu_cxx::__ops::__iter_less_iter());
5298 template<
typename _InputIterator1,
typename _InputIterator2,
5299 typename _OutputIterator,
typename _Compare>
5300 inline _OutputIterator
5301 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5302 _InputIterator2 __first2, _InputIterator2 __last2,
5303 _OutputIterator __result, _Compare __comp)
5306 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5307 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5308 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5309 typename iterator_traits<_InputIterator1>::value_type>)
5310 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5311 typename iterator_traits<_InputIterator1>::value_type,
5312 typename iterator_traits<_InputIterator2>::value_type>)
5313 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5314 typename iterator_traits<_InputIterator2>::value_type,
5315 typename iterator_traits<_InputIterator1>::value_type>)
5316 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5317 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5318 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5319 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5321 return _GLIBCXX_STD_A::__set_difference(__first1, __last1,
5322 __first2, __last2, __result,
5323 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5326 template<
typename _InputIterator1,
typename _InputIterator2,
5327 typename _OutputIterator,
5330 __set_symmetric_difference(_InputIterator1 __first1,
5331 _InputIterator1 __last1,
5332 _InputIterator2 __first2,
5333 _InputIterator2 __last2,
5334 _OutputIterator __result,
5337 while (__first1 != __last1 && __first2 != __last2)
5338 if (__comp(__first1, __first2))
5340 *__result = *__first1;
5344 else if (__comp(__first2, __first1))
5346 *__result = *__first2;
5355 return std::copy(__first2, __last2,
5356 std::copy(__first1, __last1, __result));
5376 template<
typename _InputIterator1,
typename _InputIterator2,
5377 typename _OutputIterator>
5378 inline _OutputIterator
5379 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5380 _InputIterator2 __first2, _InputIterator2 __last2,
5381 _OutputIterator __result)
5384 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5385 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5386 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5387 typename iterator_traits<_InputIterator1>::value_type>)
5388 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5389 typename iterator_traits<_InputIterator2>::value_type>)
5390 __glibcxx_function_requires(_LessThanOpConcept<
5391 typename iterator_traits<_InputIterator1>::value_type,
5392 typename iterator_traits<_InputIterator2>::value_type>)
5393 __glibcxx_function_requires(_LessThanOpConcept<
5394 typename iterator_traits<_InputIterator2>::value_type,
5395 typename iterator_traits<_InputIterator1>::value_type>)
5396 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5397 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5398 __glibcxx_requires_irreflexive2(__first1, __last1);
5399 __glibcxx_requires_irreflexive2(__first2, __last2);
5401 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5402 __first2, __last2, __result,
5403 __gnu_cxx::__ops::__iter_less_iter());
5426 template<
typename _InputIterator1,
typename _InputIterator2,
5427 typename _OutputIterator,
typename _Compare>
5428 inline _OutputIterator
5429 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5430 _InputIterator2 __first2, _InputIterator2 __last2,
5431 _OutputIterator __result,
5435 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5436 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5437 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5438 typename iterator_traits<_InputIterator1>::value_type>)
5439 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5440 typename iterator_traits<_InputIterator2>::value_type>)
5441 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5442 typename iterator_traits<_InputIterator1>::value_type,
5443 typename iterator_traits<_InputIterator2>::value_type>)
5444 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5445 typename iterator_traits<_InputIterator2>::value_type,
5446 typename iterator_traits<_InputIterator1>::value_type>)
5447 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5448 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5449 __glibcxx_requires_irreflexive_pred2(__first1, __last1, __comp);
5450 __glibcxx_requires_irreflexive_pred2(__first2, __last2, __comp);
5452 return _GLIBCXX_STD_A::__set_symmetric_difference(__first1, __last1,
5453 __first2, __last2, __result,
5454 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5457 template<
typename _ForwardIterator,
typename _Compare>
5458 _GLIBCXX14_CONSTEXPR
5460 __min_element(_ForwardIterator __first, _ForwardIterator __last,
5463 if (__first == __last)
5465 _ForwardIterator __result = __first;
5466 while (++__first != __last)
5467 if (__comp(__first, __result))
5479 template<
typename _ForwardIterator>
5480 _GLIBCXX14_CONSTEXPR
5482 inline min_element(_ForwardIterator __first, _ForwardIterator __last)
5485 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5486 __glibcxx_function_requires(_LessThanComparableConcept<
5487 typename iterator_traits<_ForwardIterator>::value_type>)
5488 __glibcxx_requires_valid_range(__first, __last);
5489 __glibcxx_requires_irreflexive(__first, __last);
5491 return _GLIBCXX_STD_A::__min_element(__first, __last,
5492 __gnu_cxx::__ops::__iter_less_iter());
5504 template<
typename _ForwardIterator,
typename _Compare>
5505 _GLIBCXX14_CONSTEXPR
5506 inline _ForwardIterator
5507 min_element(_ForwardIterator __first, _ForwardIterator __last,
5511 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5512 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5513 typename iterator_traits<_ForwardIterator>::value_type,
5514 typename iterator_traits<_ForwardIterator>::value_type>)
5515 __glibcxx_requires_valid_range(__first, __last);
5516 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5518 return _GLIBCXX_STD_A::__min_element(__first, __last,
5519 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5522 template<
typename _ForwardIterator,
typename _Compare>
5523 _GLIBCXX14_CONSTEXPR
5525 __max_element(_ForwardIterator __first, _ForwardIterator __last,
5528 if (__first == __last)
return __first;
5529 _ForwardIterator __result = __first;
5530 while (++__first != __last)
5531 if (__comp(__result, __first))
5543 template<
typename _ForwardIterator>
5544 _GLIBCXX14_CONSTEXPR
5545 inline _ForwardIterator
5546 max_element(_ForwardIterator __first, _ForwardIterator __last)
5549 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5550 __glibcxx_function_requires(_LessThanComparableConcept<
5551 typename iterator_traits<_ForwardIterator>::value_type>)
5552 __glibcxx_requires_valid_range(__first, __last);
5553 __glibcxx_requires_irreflexive(__first, __last);
5555 return _GLIBCXX_STD_A::__max_element(__first, __last,
5556 __gnu_cxx::__ops::__iter_less_iter());
5568 template<
typename _ForwardIterator,
typename _Compare>
5569 _GLIBCXX14_CONSTEXPR
5570 inline _ForwardIterator
5571 max_element(_ForwardIterator __first, _ForwardIterator __last,
5575 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5576 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5577 typename iterator_traits<_ForwardIterator>::value_type,
5578 typename iterator_traits<_ForwardIterator>::value_type>)
5579 __glibcxx_requires_valid_range(__first, __last);
5580 __glibcxx_requires_irreflexive_pred(__first, __last, __comp);
5582 return _GLIBCXX_STD_A::__max_element(__first, __last,
5583 __gnu_cxx::__ops::__iter_comp_iter(__comp));
5586 _GLIBCXX_END_NAMESPACE_ALGO
_T2 second
first is a copy of the first object
void __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last, bidirectional_iterator_tag)
void advance(_InputIterator &__i, _Distance __n)
A generalization of pointer arithmetic.
_GLIBCXX14_CONSTEXPR _ForwardIterator max_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the maximum element in a range using comparison functor.
_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)
Find the first element in a sequence for which a predicate is false.
_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.
_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.
Bidirectional iterators support a superset of forward iterator operations.
_EuclideanRingElement __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
ISO C++ entities toplevel namespace is std.
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.
_GLIBCXX14_CONSTEXPR _ForwardIterator min_element(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Return the minimum element in a range using comparison functor.
void __introsort_loop(_RandomAccessIterator __first, _RandomAccessIterator __last, _Size __depth_limit, _Compare __comp)
This is a helper function for the sort routine.
_T1 first
second_type is the second bound type
void __unguarded_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_InputIterator find_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Find the first element in a sequence for which a predicate is true.
iterator_traits< _Iter >::iterator_category __iterator_category(const _Iter &)
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.
_BidirectionalIterator1 __rotate_adaptive(_BidirectionalIterator1 __first, _BidirectionalIterator1 __middle, _BidirectionalIterator1 __last, _Distance __len1, _Distance __len2, _BidirectionalIterator2 __buffer, _Distance __buffer_size)
This is a helper function for the merge routines.
_RandomAccessIterator __unguarded_partition(_RandomAccessIterator __first, _RandomAccessIterator __last, _RandomAccessIterator __pivot, _Compare __comp)
This is a helper function...
_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.
void iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
Swaps the contents of two iterators.
iterator_traits< _InputIterator >::difference_type distance(_InputIterator __first, _InputIterator __last)
A generalization of pointer arithmetic.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
size_type requested_size() const
Returns the size requested by the constructor; may be >size().
void __heap_select(_RandomAccessIterator __first, _RandomAccessIterator __middle, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routines.
Marking output iterators.
size_type size() const
As per Table mumble.
Struct holding two objects of arbitrary type.
_ForwardIterator2 swap_ranges(_ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2)
Swap the elements of two sequences.
constexpr int __lg(int __n)
This is a helper function for the sort routines and for random.tcc.
void __inplace_stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the stable sorting routines.
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.
void __unguarded_linear_insert(_RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
iterator begin()
As per Table mumble.
Random-access iterators support a superset of bidirectional iterator operations.
Uniform discrete distribution for random numbers. A discrete random distribution on the range with e...
_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...
_ForwardIterator __rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last, forward_iterator_tag)
This is a helper function for the rotate algorithm.
Forward iterators support a superset of input iterator operations.
_RandomAccessIterator __unguarded_partition_pivot(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function...
_ForwardIterator __search_n_aux(_ForwardIterator __first, _ForwardIterator __last, _Integer __count, _UnaryPredicate __unary_pred, std::forward_iterator_tag)
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.
bool none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Checks that a predicate is false for all the elements of a sequence.
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.
_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.
_ForwardIterator rotate(_ForwardIterator __first, _ForwardIterator __middle, _ForwardIterator __last)
Rotate the elements of a sequence.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
_GLIBCXX14_CONSTEXPR pair< const _Tp &, const _Tp & > minmax(const _Tp &, const _Tp &)
Determines min and max at once as an ordered pair.
_ForwardIterator __partition(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag)
This is a helper function...
void __final_insertion_sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp)
This is a helper function for the sort routine.
_ForwardIterator is_sorted_until(_ForwardIterator __first, _ForwardIterator __last, _Compare __comp)
Determines the end of a sorted sequence using comparison functor.
_InputIterator __find_if_not(_InputIterator __first, _InputIterator __last, _Predicate __pred)
Provided for stable_partition to use.