64 #if __cplusplus >= 201103L
71 namespace std _GLIBCXX_VISIBILITY(default)
73 _GLIBCXX_BEGIN_NAMESPACE_VERSION
76 template<
typename _Iterator>
81 __glibcxx_function_requires(_LessThanComparableConcept<
82 typename iterator_traits<_Iterator>::value_type>)
100 template<
typename _Iterator,
typename _Compare>
106 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,
bool,
107 typename iterator_traits<_Iterator>::value_type,
108 typename iterator_traits<_Iterator>::value_type>)
110 if (__comp(*__a, *__b))
112 if (__comp(*__b, *__c))
114 else if (__comp(*__a, *__c))
117 else if (__comp(*__a, *__c))
119 else if (__comp(*__b, *__c))
128 template<
typename _InputIterator,
typename _Tp>
129 inline _InputIterator
130 __find(_InputIterator __first, _InputIterator __last,
133 while (__first != __last && !(*__first == __val))
139 template<
typename _InputIterator,
typename _Predicate>
140 inline _InputIterator
141 __find_if(_InputIterator __first, _InputIterator __last,
144 while (__first != __last && !
bool(__pred(*__first)))
150 template<
typename _RandomAccessIterator,
typename _Tp>
151 _RandomAccessIterator
152 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
155 typename iterator_traits<_RandomAccessIterator>::difference_type
156 __trip_count = (__last - __first) >> 2;
158 for (; __trip_count > 0; --__trip_count)
160 if (*__first == __val)
164 if (*__first == __val)
168 if (*__first == __val)
172 if (*__first == __val)
177 switch (__last - __first)
180 if (*__first == __val)
184 if (*__first == __val)
188 if (*__first == __val)
198 template<
typename _RandomAccessIterator,
typename _Predicate>
199 _RandomAccessIterator
200 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
203 typename iterator_traits<_RandomAccessIterator>::difference_type
204 __trip_count = (__last - __first) >> 2;
206 for (; __trip_count > 0; --__trip_count)
208 if (__pred(*__first))
212 if (__pred(*__first))
216 if (__pred(*__first))
220 if (__pred(*__first))
225 switch (__last - __first)
228 if (__pred(*__first))
232 if (__pred(*__first))
236 if (__pred(*__first))
246 template<
typename _InputIterator,
typename _Predicate>
247 inline _InputIterator
251 while (__first != __last &&
bool(__pred(*__first)))
257 template<
typename _RandomAccessIterator,
typename _Predicate>
258 _RandomAccessIterator
262 typename iterator_traits<_RandomAccessIterator>::difference_type
263 __trip_count = (__last - __first) >> 2;
265 for (; __trip_count > 0; --__trip_count)
267 if (!
bool(__pred(*__first)))
271 if (!
bool(__pred(*__first)))
275 if (!
bool(__pred(*__first)))
279 if (!
bool(__pred(*__first)))
284 switch (__last - __first)
287 if (!
bool(__pred(*__first)))
291 if (!
bool(__pred(*__first)))
295 if (!
bool(__pred(*__first)))
305 template<
typename _InputIterator,
typename _Predicate>
306 inline _InputIterator
317 template<
typename _InputIterator,
typename _Predicate,
typename _Distance>
321 for (; __len; --__len, ++__first)
322 if (!
bool(__pred(*__first)))
345 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
347 __search_n(_ForwardIterator __first, _ForwardIterator __last,
348 _Integer __count,
const _Tp& __val,
351 __first = _GLIBCXX_STD_A::find(__first, __last, __val);
352 while (__first != __last)
354 typename iterator_traits<_ForwardIterator>::difference_type
356 _ForwardIterator __i = __first;
358 while (__i != __last && __n != 1 && *__i == __val)
367 __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
377 template<
typename _RandomAccessIter,
typename _Integer,
typename _Tp>
379 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
380 _Integer __count,
const _Tp& __val,
384 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
387 _DistanceType __tailSize = __last - __first;
388 const _DistanceType __pattSize = __count;
390 if (__tailSize < __pattSize)
393 const _DistanceType __skipOffset = __pattSize - 1;
394 _RandomAccessIter __lookAhead = __first + __skipOffset;
395 __tailSize -= __pattSize;
401 while (!(*__lookAhead == __val))
403 if (__tailSize < __pattSize)
405 __lookAhead += __pattSize;
406 __tailSize -= __pattSize;
408 _DistanceType __remainder = __skipOffset;
409 for (_RandomAccessIter __backTrack = __lookAhead - 1;
410 *__backTrack == __val; --__backTrack)
412 if (--__remainder == 0)
413 return (__lookAhead - __skipOffset);
415 if (__remainder > __tailSize)
417 __lookAhead += __remainder;
418 __tailSize -= __remainder;
430 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
431 typename _BinaryPredicate>
433 __search_n(_ForwardIterator __first, _ForwardIterator __last,
434 _Integer __count,
const _Tp& __val,
437 while (__first != __last && !
bool(__binary_pred(*__first, __val)))
440 while (__first != __last)
442 typename iterator_traits<_ForwardIterator>::difference_type
444 _ForwardIterator __i = __first;
446 while (__i != __last && __n != 1 &&
bool(__binary_pred(*__i, __val)))
456 while (__first != __last
457 && !
bool(__binary_pred(*__first, __val)))
469 template<
typename _RandomAccessIter,
typename _Integer,
typename _Tp,
470 typename _BinaryPredicate>
472 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
473 _Integer __count,
const _Tp& __val,
477 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
480 _DistanceType __tailSize = __last - __first;
481 const _DistanceType __pattSize = __count;
483 if (__tailSize < __pattSize)
486 const _DistanceType __skipOffset = __pattSize - 1;
487 _RandomAccessIter __lookAhead = __first + __skipOffset;
488 __tailSize -= __pattSize;
494 while (!
bool(__binary_pred(*__lookAhead, __val)))
496 if (__tailSize < __pattSize)
498 __lookAhead += __pattSize;
499 __tailSize -= __pattSize;
501 _DistanceType __remainder = __skipOffset;
502 for (_RandomAccessIter __backTrack = __lookAhead - 1;
503 __binary_pred(*__backTrack, __val); --__backTrack)
505 if (--__remainder == 0)
506 return (__lookAhead - __skipOffset);
508 if (__remainder > __tailSize)
510 __lookAhead += __remainder;
511 __tailSize -= __remainder;
516 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
518 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
519 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
520 forward_iterator_tag, forward_iterator_tag)
522 if (__first2 == __last2)
526 _ForwardIterator1 __result = __last1;
529 _ForwardIterator1 __new_result
530 = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
531 if (__new_result == __last1)
535 __result = __new_result;
536 __first1 = __new_result;
543 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
544 typename _BinaryPredicate>
546 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
547 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
548 forward_iterator_tag, forward_iterator_tag,
549 _BinaryPredicate __comp)
551 if (__first2 == __last2)
555 _ForwardIterator1 __result = __last1;
558 _ForwardIterator1 __new_result
559 = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
561 if (__new_result == __last1)
565 __result = __new_result;
566 __first1 = __new_result;
574 template<
typename _B
idirectionalIterator1,
typename _B
idirectionalIterator2>
575 _BidirectionalIterator1
576 __find_end(_BidirectionalIterator1 __first1,
577 _BidirectionalIterator1 __last1,
578 _BidirectionalIterator2 __first2,
579 _BidirectionalIterator2 __last2,
580 bidirectional_iterator_tag, bidirectional_iterator_tag)
583 __glibcxx_function_requires(_BidirectionalIteratorConcept<
584 _BidirectionalIterator1>)
585 __glibcxx_function_requires(_BidirectionalIteratorConcept<
586 _BidirectionalIterator2>)
588 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
589 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
591 _RevIterator1 __rlast1(__first1);
592 _RevIterator2 __rlast2(__first2);
593 _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
595 _RevIterator2(__last2),
598 if (__rresult == __rlast1)
602 _BidirectionalIterator1 __result = __rresult.base();
608 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
609 typename _BinaryPredicate>
610 _BidirectionalIterator1
611 __find_end(_BidirectionalIterator1 __first1,
612 _BidirectionalIterator1 __last1,
613 _BidirectionalIterator2 __first2,
614 _BidirectionalIterator2 __last2,
615 bidirectional_iterator_tag, bidirectional_iterator_tag,
616 _BinaryPredicate __comp)
619 __glibcxx_function_requires(_BidirectionalIteratorConcept<
620 _BidirectionalIterator1>)
621 __glibcxx_function_requires(_BidirectionalIteratorConcept<
622 _BidirectionalIterator2>)
624 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
625 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
627 _RevIterator1 __rlast1(__first1);
628 _RevIterator2 __rlast2(__first2);
629 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
630 _RevIterator2(__last2), __rlast2,
633 if (__rresult == __rlast1)
637 _BidirectionalIterator1 __result = __rresult.base();
669 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
670 inline _ForwardIterator1
671 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
672 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
675 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
676 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
677 __glibcxx_function_requires(_EqualOpConcept<
678 typename iterator_traits<_ForwardIterator1>::value_type,
679 typename iterator_traits<_ForwardIterator2>::value_type>)
680 __glibcxx_requires_valid_range(__first1, __last1);
681 __glibcxx_requires_valid_range(__first2, __last2);
683 return std::__find_end(__first1, __last1, __first2, __last2,
716 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
717 typename _BinaryPredicate>
718 inline _ForwardIterator1
719 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
720 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
721 _BinaryPredicate __comp)
724 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
725 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
726 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
727 typename iterator_traits<_ForwardIterator1>::value_type,
728 typename iterator_traits<_ForwardIterator2>::value_type>)
729 __glibcxx_requires_valid_range(__first1, __last1);
730 __glibcxx_requires_valid_range(__first2, __last2);
732 return std::__find_end(__first1, __last1, __first2, __last2,
738 #if __cplusplus >= 201103L
751 template<
typename _InputIterator,
typename _Predicate>
753 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
768 template<
typename _InputIterator,
typename _Predicate>
770 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
771 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
786 template<
typename _InputIterator,
typename _Predicate>
788 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
801 template<
typename _InputIterator,
typename _Predicate>
802 inline _InputIterator
803 find_if_not(_InputIterator __first, _InputIterator __last,
807 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
808 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
809 typename iterator_traits<_InputIterator>::value_type>)
810 __glibcxx_requires_valid_range(__first, __last);
824 template<
typename _InputIterator,
typename _Predicate>
826 is_partitioned(_InputIterator __first, _InputIterator __last,
842 template<
typename _ForwardIterator,
typename _Predicate>
844 partition_point(_ForwardIterator __first, _ForwardIterator __last,
848 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
849 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
850 typename iterator_traits<_ForwardIterator>::value_type>)
853 __glibcxx_requires_valid_range(__first, __last);
855 typedef typename iterator_traits<_ForwardIterator>::difference_type
859 _DistanceType __half;
860 _ForwardIterator __middle;
867 if (__pred(*__middle))
871 __len = __len - __half - 1;
895 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
897 remove_copy(_InputIterator __first, _InputIterator __last,
898 _OutputIterator __result,
const _Tp& __value)
901 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
902 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
903 typename iterator_traits<_InputIterator>::value_type>)
904 __glibcxx_function_requires(_EqualOpConcept<
905 typename iterator_traits<_InputIterator>::value_type, _Tp>)
906 __glibcxx_requires_valid_range(__first, __last);
908 for (; __first != __last; ++__first)
909 if (!(*__first == __value))
911 *__result = *__first;
932 template<
typename _InputIterator,
typename _OutputIterator,
935 remove_copy_if(_InputIterator __first, _InputIterator __last,
936 _OutputIterator __result, _Predicate __pred)
939 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
940 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
941 typename iterator_traits<_InputIterator>::value_type>)
942 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
943 typename iterator_traits<_InputIterator>::value_type>)
944 __glibcxx_requires_valid_range(__first, __last);
946 for (; __first != __last; ++__first)
947 if (!
bool(__pred(*__first)))
949 *__result = *__first;
955 #if __cplusplus >= 201103L
971 template<
typename _InputIterator,
typename _OutputIterator,
974 copy_if(_InputIterator __first, _InputIterator __last,
975 _OutputIterator __result, _Predicate __pred)
978 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
979 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
980 typename iterator_traits<_InputIterator>::value_type>)
981 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
982 typename iterator_traits<_InputIterator>::value_type>)
983 __glibcxx_requires_valid_range(__first, __last);
985 for (; __first != __last; ++__first)
986 if (__pred(*__first))
988 *__result = *__first;
995 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
997 __copy_n(_InputIterator __first, _Size __n,
998 _OutputIterator __result, input_iterator_tag)
1004 *__result = *__first;
1015 template<
typename _RandomAccessIterator,
typename _Size,
1016 typename _OutputIterator>
1017 inline _OutputIterator
1018 __copy_n(_RandomAccessIterator __first, _Size __n,
1019 _OutputIterator __result, random_access_iterator_tag)
1020 {
return std::copy(__first, __first + __n, __result); }
1035 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
1036 inline _OutputIterator
1037 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1040 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1041 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1042 typename iterator_traits<_InputIterator>::value_type>)
1044 return std::__copy_n(__first, __n, __result,
1063 template<
typename _InputIterator,
typename _OutputIterator1,
1064 typename _OutputIterator2,
typename _Predicate>
1065 pair<_OutputIterator1, _OutputIterator2>
1066 partition_copy(_InputIterator __first, _InputIterator __last,
1067 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1071 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1072 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1073 typename iterator_traits<_InputIterator>::value_type>)
1074 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1075 typename iterator_traits<_InputIterator>::value_type>)
1076 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1077 typename iterator_traits<_InputIterator>::value_type>)
1078 __glibcxx_requires_valid_range(__first, __last);
1080 for (; __first != __last; ++__first)
1081 if (__pred(*__first))
1083 *__out_true = *__first;
1088 *__out_false = *__first;
1113 template<
typename _ForwardIterator,
typename _Tp>
1115 remove(_ForwardIterator __first, _ForwardIterator __last,
1119 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1121 __glibcxx_function_requires(_EqualOpConcept<
1122 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1123 __glibcxx_requires_valid_range(__first, __last);
1125 __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1126 if(__first == __last)
1128 _ForwardIterator __result = __first;
1130 for(; __first != __last; ++__first)
1131 if(!(*__first == __value))
1133 *__result = _GLIBCXX_MOVE(*__first);
1156 template<
typename _ForwardIterator,
typename _Predicate>
1158 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1162 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1164 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1165 typename iterator_traits<_ForwardIterator>::value_type>)
1166 __glibcxx_requires_valid_range(__first, __last);
1168 __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1169 if(__first == __last)
1171 _ForwardIterator __result = __first;
1173 for(; __first != __last; ++__first)
1174 if(!
bool(__pred(*__first)))
1176 *__result = _GLIBCXX_MOVE(*__first);
1196 template<
typename _ForwardIterator>
1198 unique(_ForwardIterator __first, _ForwardIterator __last)
1201 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1203 __glibcxx_function_requires(_EqualityComparableConcept<
1204 typename iterator_traits<_ForwardIterator>::value_type>)
1205 __glibcxx_requires_valid_range(__first, __last);
1208 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1209 if (__first == __last)
1213 _ForwardIterator __dest = __first;
1215 while (++__first != __last)
1216 if (!(*__dest == *__first))
1217 *++__dest = _GLIBCXX_MOVE(*__first);
1236 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1238 unique(_ForwardIterator __first, _ForwardIterator __last,
1239 _BinaryPredicate __binary_pred)
1242 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1244 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1245 typename iterator_traits<_ForwardIterator>::value_type,
1246 typename iterator_traits<_ForwardIterator>::value_type>)
1247 __glibcxx_requires_valid_range(__first, __last);
1250 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1251 if (__first == __last)
1255 _ForwardIterator __dest = __first;
1257 while (++__first != __last)
1258 if (!
bool(__binary_pred(*__dest, *__first)))
1259 *++__dest = _GLIBCXX_MOVE(*__first);
1268 template<
typename _ForwardIterator,
typename _OutputIterator>
1271 _OutputIterator __result,
1275 _ForwardIterator __next = __first;
1276 *__result = *__first;
1277 while (++__next != __last)
1278 if (!(*__first == *__next))
1281 *++__result = *__first;
1291 template<
typename _InputIterator,
typename _OutputIterator>
1294 _OutputIterator __result,
1298 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1299 *__result = __value;
1300 while (++__first != __last)
1301 if (!(__value == *__first))
1304 *++__result = __value;
1314 template<
typename _InputIterator,
typename _ForwardIterator>
1317 _ForwardIterator __result,
1321 *__result = *__first;
1322 while (++__first != __last)
1323 if (!(*__result == *__first))
1324 *++__result = *__first;
1334 template<
typename _ForwardIterator,
typename _OutputIterator,
1335 typename _BinaryPredicate>
1338 _OutputIterator __result, _BinaryPredicate __binary_pred,
1342 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1343 typename iterator_traits<_ForwardIterator>::value_type,
1344 typename iterator_traits<_ForwardIterator>::value_type>)
1346 _ForwardIterator __next = __first;
1347 *__result = *__first;
1348 while (++__next != __last)
1349 if (!
bool(__binary_pred(*__first, *__next)))
1352 *++__result = *__first;
1363 template<
typename _InputIterator,
typename _OutputIterator,
1364 typename _BinaryPredicate>
1367 _OutputIterator __result, _BinaryPredicate __binary_pred,
1371 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1372 typename iterator_traits<_InputIterator>::value_type,
1373 typename iterator_traits<_InputIterator>::value_type>)
1375 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1376 *__result = __value;
1377 while (++__first != __last)
1378 if (!
bool(__binary_pred(__value, *__first)))
1381 *++__result = __value;
1392 template<
typename _InputIterator,
typename _ForwardIterator,
1393 typename _BinaryPredicate>
1396 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1400 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1401 typename iterator_traits<_ForwardIterator>::value_type,
1402 typename iterator_traits<_InputIterator>::value_type>)
1404 *__result = *__first;
1405 while (++__first != __last)
1406 if (!
bool(__binary_pred(*__result, *__first)))
1407 *++__result = *__first;
1416 template<
typename _B
idirectionalIterator>
1418 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1422 if (__first == __last || __first == --__last)
1436 template<
typename _RandomAccessIterator>
1438 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1441 if (__first == __last)
1444 while (__first < __last)
1464 template<
typename _B
idirectionalIterator>
1466 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1469 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1470 _BidirectionalIterator>)
1471 __glibcxx_requires_valid_range(__first, __last);
1491 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1493 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1494 _OutputIterator __result)
1497 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1498 _BidirectionalIterator>)
1499 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1500 typename iterator_traits<_BidirectionalIterator>::value_type>)
1501 __glibcxx_requires_valid_range(__first, __last);
1503 while (__first != __last)
1506 *__result = *__last;
1516 template<
typename _Eucl
ideanRingElement>
1517 _EuclideanRingElement
1518 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1522 _EuclideanRingElement __t = __m % __n;
1530 template<
typename _ForwardIterator>
1533 _ForwardIterator __middle,
1534 _ForwardIterator __last,
1537 if (__first == __middle || __last == __middle)
1540 _ForwardIterator __first2 = __middle;
1546 if (__first == __middle)
1547 __middle = __first2;
1549 while (__first2 != __last);
1551 __first2 = __middle;
1553 while (__first2 != __last)
1558 if (__first == __middle)
1559 __middle = __first2;
1560 else if (__first2 == __last)
1561 __first2 = __middle;
1566 template<
typename _B
idirectionalIterator>
1569 _BidirectionalIterator __middle,
1570 _BidirectionalIterator __last,
1574 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1575 _BidirectionalIterator>)
1577 if (__first == __middle || __last == __middle)
1583 while (__first != __middle && __middle != __last)
1589 if (__first == __middle)
1596 template<
typename _RandomAccessIterator>
1599 _RandomAccessIterator __middle,
1600 _RandomAccessIterator __last,
1604 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1605 _RandomAccessIterator>)
1607 if (__first == __middle || __last == __middle)
1610 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1612 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1615 _Distance __n = __last - __first;
1616 _Distance __k = __middle - __first;
1618 if (__k == __n - __k)
1624 _RandomAccessIterator __p = __first;
1628 if (__k < __n - __k)
1630 if (__is_pod(_ValueType) && __k == 1)
1632 _ValueType __t = _GLIBCXX_MOVE(*__p);
1633 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1634 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1637 _RandomAccessIterator __q = __p + __k;
1638 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1647 std::swap(__n, __k);
1653 if (__is_pod(_ValueType) && __k == 1)
1655 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1656 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1657 *__p = _GLIBCXX_MOVE(__t);
1660 _RandomAccessIterator __q = __p + __n;
1662 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1671 std::swap(__n, __k);
1697 template<
typename _ForwardIterator>
1699 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1700 _ForwardIterator __last)
1703 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1705 __glibcxx_requires_valid_range(__first, __middle);
1706 __glibcxx_requires_valid_range(__middle, __last);
1708 typedef typename iterator_traits<_ForwardIterator>::iterator_category
1733 template<
typename _ForwardIterator,
typename _OutputIterator>
1735 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1736 _ForwardIterator __last, _OutputIterator __result)
1739 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1740 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1741 typename iterator_traits<_ForwardIterator>::value_type>)
1742 __glibcxx_requires_valid_range(__first, __middle);
1743 __glibcxx_requires_valid_range(__middle, __last);
1745 return std::copy(__first, __middle,
1746 std::copy(__middle, __last, __result));
1750 template<
typename _ForwardIterator,
typename _Predicate>
1755 if (__first == __last)
1758 while (__pred(*__first))
1759 if (++__first == __last)
1762 _ForwardIterator __next = __first;
1764 while (++__next != __last)
1765 if (__pred(*__next))
1775 template<
typename _B
idirectionalIterator,
typename _Predicate>
1776 _BidirectionalIterator
1777 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1783 if (__first == __last)
1785 else if (__pred(*__first))
1791 if (__first == __last)
1793 else if (!
bool(__pred(*__last)))
1807 template<
typename _ForwardIterator,
typename _Predicate,
typename _Distance>
1810 _Predicate __pred, _Distance __len)
1814 _ForwardIterator __middle = __first;
1816 _ForwardIterator __left_split =
1820 _Distance __right_len = __len - __len / 2;
1821 _ForwardIterator __right_split =
1827 std::rotate(__left_split, __middle, __right_split);
1829 return __left_split;
1838 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1842 _ForwardIterator __last,
1843 _Predicate __pred, _Distance __len,
1845 _Distance __buffer_size)
1847 if (__len <= __buffer_size)
1849 _ForwardIterator __result1 = __first;
1850 _Pointer __result2 = __buffer;
1854 *__result2 = _GLIBCXX_MOVE(*__first);
1857 for (; __first != __last; ++__first)
1858 if (__pred(*__first))
1860 *__result1 = _GLIBCXX_MOVE(*__first);
1865 *__result2 = _GLIBCXX_MOVE(*__first);
1868 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1873 _ForwardIterator __middle = __first;
1875 _ForwardIterator __left_split =
1877 __len / 2, __buffer,
1881 _Distance __right_len = __len - __len / 2;
1882 _ForwardIterator __right_split =
1888 __buffer, __buffer_size);
1889 std::rotate(__left_split, __middle, __right_split);
1891 return __left_split;
1912 template<
typename _ForwardIterator,
typename _Predicate>
1914 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1918 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1920 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1921 typename iterator_traits<_ForwardIterator>::value_type>)
1922 __glibcxx_requires_valid_range(__first, __last);
1926 if (__first == __last)
1930 typedef typename iterator_traits<_ForwardIterator>::value_type
1932 typedef typename iterator_traits<_ForwardIterator>::difference_type
1937 if (__buf.
size() > 0)
1942 _DistanceType(__buf.
size()));
1951 template<
typename _RandomAccessIterator>
1954 _RandomAccessIterator __middle,
1955 _RandomAccessIterator __last)
1958 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1959 if (*__i < *__first)
1960 std::__pop_heap(__first, __middle, __i);
1964 template<
typename _RandomAccessIterator,
typename _Compare>
1967 _RandomAccessIterator __middle,
1968 _RandomAccessIterator __last, _Compare __comp)
1971 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1972 if (__comp(*__i, *__first))
1973 std::__pop_heap(__first, __middle, __i, __comp);
1996 template<
typename _InputIterator,
typename _RandomAccessIterator>
1997 _RandomAccessIterator
1998 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1999 _RandomAccessIterator __result_first,
2000 _RandomAccessIterator __result_last)
2002 typedef typename iterator_traits<_InputIterator>::value_type
2004 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2006 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2010 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2011 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2013 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
2015 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
2016 __glibcxx_requires_valid_range(__first, __last);
2017 __glibcxx_requires_valid_range(__result_first, __result_last);
2019 if (__result_first == __result_last)
2020 return __result_last;
2021 _RandomAccessIterator __result_real_last = __result_first;
2022 while(__first != __last && __result_real_last != __result_last)
2024 *__result_real_last = *__first;
2025 ++__result_real_last;
2029 while (__first != __last)
2031 if (*__first < *__result_first)
2032 std::__adjust_heap(__result_first, _DistanceType(0),
2033 _DistanceType(__result_real_last
2035 _InputValueType(*__first));
2039 return __result_real_last;
2062 template<
typename _InputIterator,
typename _RandomAccessIterator,
typename _Compare>
2063 _RandomAccessIterator
2064 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2065 _RandomAccessIterator __result_first,
2066 _RandomAccessIterator __result_last,
2069 typedef typename iterator_traits<_InputIterator>::value_type
2071 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2073 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2077 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2078 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2079 _RandomAccessIterator>)
2080 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2082 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2083 _InputValueType, _OutputValueType>)
2084 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2085 _OutputValueType, _OutputValueType>)
2086 __glibcxx_requires_valid_range(__first, __last);
2087 __glibcxx_requires_valid_range(__result_first, __result_last);
2089 if (__result_first == __result_last)
2090 return __result_last;
2091 _RandomAccessIterator __result_real_last = __result_first;
2092 while(__first != __last && __result_real_last != __result_last)
2094 *__result_real_last = *__first;
2095 ++__result_real_last;
2099 while (__first != __last)
2101 if (__comp(*__first, *__result_first))
2102 std::__adjust_heap(__result_first, _DistanceType(0),
2103 _DistanceType(__result_real_last
2105 _InputValueType(*__first),
2110 return __result_real_last;
2114 template<
typename _RandomAccessIterator>
2118 typename iterator_traits<_RandomAccessIterator>::value_type
2119 __val = _GLIBCXX_MOVE(*__last);
2120 _RandomAccessIterator __next = __last;
2122 while (__val < *__next)
2124 *__last = _GLIBCXX_MOVE(*__next);
2128 *__last = _GLIBCXX_MOVE(__val);
2132 template<
typename _RandomAccessIterator,
typename _Compare>
2137 typename iterator_traits<_RandomAccessIterator>::value_type
2138 __val = _GLIBCXX_MOVE(*__last);
2139 _RandomAccessIterator __next = __last;
2141 while (__comp(__val, *__next))
2143 *__last = _GLIBCXX_MOVE(*__next);
2147 *__last = _GLIBCXX_MOVE(__val);
2151 template<
typename _RandomAccessIterator>
2154 _RandomAccessIterator __last)
2156 if (__first == __last)
2159 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2161 if (*__i < *__first)
2163 typename iterator_traits<_RandomAccessIterator>::value_type
2164 __val = _GLIBCXX_MOVE(*__i);
2165 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2166 *__first = _GLIBCXX_MOVE(__val);
2174 template<
typename _RandomAccessIterator,
typename _Compare>
2177 _RandomAccessIterator __last, _Compare __comp)
2179 if (__first == __last)
return;
2181 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2183 if (__comp(*__i, *__first))
2185 typename iterator_traits<_RandomAccessIterator>::value_type
2186 __val = _GLIBCXX_MOVE(*__i);
2187 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2188 *__first = _GLIBCXX_MOVE(__val);
2196 template<
typename _RandomAccessIterator>
2199 _RandomAccessIterator __last)
2201 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2204 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2209 template<
typename _RandomAccessIterator,
typename _Compare>
2212 _RandomAccessIterator __last, _Compare __comp)
2214 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2217 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2225 enum { _S_threshold = 16 };
2228 template<
typename _RandomAccessIterator>
2231 _RandomAccessIterator __last)
2233 if (__last - __first >
int(_S_threshold))
2243 template<
typename _RandomAccessIterator,
typename _Compare>
2246 _RandomAccessIterator __last, _Compare __comp)
2248 if (__last - __first >
int(_S_threshold))
2259 template<
typename _RandomAccessIterator,
typename _Tp>
2260 _RandomAccessIterator
2262 _RandomAccessIterator __last,
const _Tp& __pivot)
2266 while (*__first < __pivot)
2269 while (__pivot < *__last)
2271 if (!(__first < __last))
2279 template<
typename _RandomAccessIterator,
typename _Tp,
typename _Compare>
2280 _RandomAccessIterator
2282 _RandomAccessIterator __last,
2283 const _Tp& __pivot, _Compare __comp)
2287 while (__comp(*__first, __pivot))
2290 while (__comp(__pivot, *__last))
2292 if (!(__first < __last))
2300 template<
typename _RandomAccessIterator>
2301 inline _RandomAccessIterator
2303 _RandomAccessIterator __last)
2305 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2312 template<
typename _RandomAccessIterator,
typename _Compare>
2313 inline _RandomAccessIterator
2315 _RandomAccessIterator __last, _Compare __comp)
2317 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2323 template<
typename _RandomAccessIterator,
typename _Size>
2326 _RandomAccessIterator __last,
2327 _Size __depth_limit)
2329 while (__last - __first >
int(_S_threshold))
2331 if (__depth_limit == 0)
2333 _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2337 _RandomAccessIterator __cut =
2345 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2348 _RandomAccessIterator __last,
2349 _Size __depth_limit, _Compare __comp)
2351 while (__last - __first >
int(_S_threshold))
2353 if (__depth_limit == 0)
2355 _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2359 _RandomAccessIterator __cut =
2368 template<
typename _RandomAccessIterator,
typename _Size>
2370 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2371 _RandomAccessIterator __last, _Size __depth_limit)
2373 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2376 while (__last - __first > 3)
2378 if (__depth_limit == 0)
2383 std::iter_swap(__first, __nth);
2387 _RandomAccessIterator __cut =
2397 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2399 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2400 _RandomAccessIterator __last, _Size __depth_limit,
2403 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2406 while (__last - __first > 3)
2408 if (__depth_limit == 0)
2416 _RandomAccessIterator __cut =
2446 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2448 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2449 const _Tp& __val, _Compare __comp)
2451 typedef typename iterator_traits<_ForwardIterator>::value_type
2453 typedef typename iterator_traits<_ForwardIterator>::difference_type
2457 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2458 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2460 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2467 _DistanceType __half = __len >> 1;
2468 _ForwardIterator __middle = __first;
2470 if (__comp(*__middle, __val))
2474 __len = __len - __half - 1;
2493 template<
typename _ForwardIterator,
typename _Tp>
2495 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2498 typedef typename iterator_traits<_ForwardIterator>::value_type
2500 typedef typename iterator_traits<_ForwardIterator>::difference_type
2504 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2505 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2506 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2512 _DistanceType __half = __len >> 1;
2513 _ForwardIterator __middle = __first;
2515 if (__val < *__middle)
2521 __len = __len - __half - 1;
2542 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2544 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2545 const _Tp& __val, _Compare __comp)
2547 typedef typename iterator_traits<_ForwardIterator>::value_type
2549 typedef typename iterator_traits<_ForwardIterator>::difference_type
2553 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2554 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2556 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2563 _DistanceType __half = __len >> 1;
2564 _ForwardIterator __middle = __first;
2566 if (__comp(__val, *__middle))
2572 __len = __len - __half - 1;
2595 template<
typename _ForwardIterator,
typename _Tp>
2596 pair<_ForwardIterator, _ForwardIterator>
2597 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2600 typedef typename iterator_traits<_ForwardIterator>::value_type
2602 typedef typename iterator_traits<_ForwardIterator>::difference_type
2606 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2607 __glibcxx_function_requires(_LessThanOpConcept<_ValueType, _Tp>)
2608 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2609 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2610 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2616 _DistanceType __half = __len >> 1;
2617 _ForwardIterator __middle = __first;
2619 if (*__middle < __val)
2623 __len = __len - __half - 1;
2625 else if (__val < *__middle)
2657 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2658 pair<_ForwardIterator, _ForwardIterator>
2659 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2660 const _Tp& __val, _Compare __comp)
2662 typedef typename iterator_traits<_ForwardIterator>::value_type
2664 typedef typename iterator_traits<_ForwardIterator>::difference_type
2668 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2669 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2671 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2673 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2675 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2682 _DistanceType __half = __len >> 1;
2683 _ForwardIterator __middle = __first;
2685 if (__comp(*__middle, __val))
2689 __len = __len - __half - 1;
2691 else if (__comp(__val, *__middle))
2718 template<
typename _ForwardIterator,
typename _Tp>
2720 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2723 typedef typename iterator_traits<_ForwardIterator>::value_type
2727 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2728 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2729 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2730 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2733 return __i != __last && !(__val < *__i);
2751 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2753 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2754 const _Tp& __val, _Compare __comp)
2756 typedef typename iterator_traits<_ForwardIterator>::value_type
2760 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2761 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2763 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2765 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2769 return __i != __last && !bool(__comp(__val, *__i));
2775 template<
typename _InputIterator1,
typename _InputIterator2,
2776 typename _OutputIterator>
2779 _InputIterator2 __first2, _InputIterator2 __last2,
2780 _OutputIterator __result)
2782 while (__first1 != __last1 && __first2 != __last2)
2784 if (*__first2 < *__first1)
2786 *__result = _GLIBCXX_MOVE(*__first2);
2791 *__result = _GLIBCXX_MOVE(*__first1);
2796 if (__first1 != __last1)
2797 _GLIBCXX_MOVE3(__first1, __last1, __result);
2801 template<
typename _InputIterator1,
typename _InputIterator2,
2802 typename _OutputIterator,
typename _Compare>
2805 _InputIterator2 __first2, _InputIterator2 __last2,
2806 _OutputIterator __result, _Compare __comp)
2808 while (__first1 != __last1 && __first2 != __last2)
2810 if (__comp(*__first2, *__first1))
2812 *__result = _GLIBCXX_MOVE(*__first2);
2817 *__result = _GLIBCXX_MOVE(*__first1);
2822 if (__first1 != __last1)
2823 _GLIBCXX_MOVE3(__first1, __last1, __result);
2827 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2828 typename _BidirectionalIterator3>
2831 _BidirectionalIterator1 __last1,
2832 _BidirectionalIterator2 __first2,
2833 _BidirectionalIterator2 __last2,
2834 _BidirectionalIterator3 __result)
2836 if (__first1 == __last1)
2838 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2841 else if (__first2 == __last2)
2848 if (*__last2 < *__last1)
2850 *--__result = _GLIBCXX_MOVE(*__last1);
2851 if (__first1 == __last1)
2853 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2860 *--__result = _GLIBCXX_MOVE(*__last2);
2861 if (__first2 == __last2)
2869 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2870 typename _BidirectionalIterator3,
typename _Compare>
2873 _BidirectionalIterator1 __last1,
2874 _BidirectionalIterator2 __first2,
2875 _BidirectionalIterator2 __last2,
2876 _BidirectionalIterator3 __result,
2879 if (__first1 == __last1)
2881 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2884 else if (__first2 == __last2)
2891 if (__comp(*__last2, *__last1))
2893 *--__result = _GLIBCXX_MOVE(*__last1);
2894 if (__first1 == __last1)
2896 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2903 *--__result = _GLIBCXX_MOVE(*__last2);
2904 if (__first2 == __last2)
2912 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2914 _BidirectionalIterator1
2916 _BidirectionalIterator1 __middle,
2917 _BidirectionalIterator1 __last,
2918 _Distance __len1, _Distance __len2,
2919 _BidirectionalIterator2 __buffer,
2920 _Distance __buffer_size)
2922 _BidirectionalIterator2 __buffer_end;
2923 if (__len1 > __len2 && __len2 <= __buffer_size)
2927 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2928 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2929 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2934 else if (__len1 <= __buffer_size)
2938 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2939 _GLIBCXX_MOVE3(__middle, __last, __first);
2940 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2954 template<
typename _BidirectionalIterator,
typename _Distance,
2958 _BidirectionalIterator __middle,
2959 _BidirectionalIterator __last,
2960 _Distance __len1, _Distance __len2,
2961 _Pointer __buffer, _Distance __buffer_size)
2963 if (__len1 <= __len2 && __len1 <= __buffer_size)
2965 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2969 else if (__len2 <= __buffer_size)
2971 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2973 __buffer_end, __last);
2977 _BidirectionalIterator __first_cut = __first;
2978 _BidirectionalIterator __second_cut = __middle;
2979 _Distance __len11 = 0;
2980 _Distance __len22 = 0;
2981 if (__len1 > __len2)
2983 __len11 = __len1 / 2;
2991 __len22 = __len2 / 2;
2997 _BidirectionalIterator __new_middle =
2999 __len1 - __len11, __len22, __buffer,
3002 __len22, __buffer, __buffer_size);
3005 __len2 - __len22, __buffer, __buffer_size);
3010 template<
typename _BidirectionalIterator,
typename _Distance,
3011 typename _Pointer,
typename _Compare>
3014 _BidirectionalIterator __middle,
3015 _BidirectionalIterator __last,
3016 _Distance __len1, _Distance __len2,
3017 _Pointer __buffer, _Distance __buffer_size,
3020 if (__len1 <= __len2 && __len1 <= __buffer_size)
3022 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
3026 else if (__len2 <= __buffer_size)
3028 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
3030 __buffer_end, __last, __comp);
3034 _BidirectionalIterator __first_cut = __first;
3035 _BidirectionalIterator __second_cut = __middle;
3036 _Distance __len11 = 0;
3037 _Distance __len22 = 0;
3038 if (__len1 > __len2)
3040 __len11 = __len1 / 2;
3048 __len22 = __len2 / 2;
3054 _BidirectionalIterator __new_middle =
3056 __len1 - __len11, __len22, __buffer,
3059 __len22, __buffer, __buffer_size, __comp);
3062 __len2 - __len22, __buffer,
3063 __buffer_size, __comp);
3068 template<
typename _B
idirectionalIterator,
typename _Distance>
3071 _BidirectionalIterator __middle,
3072 _BidirectionalIterator __last,
3073 _Distance __len1, _Distance __len2)
3075 if (__len1 == 0 || __len2 == 0)
3077 if (__len1 + __len2 == 2)
3079 if (*__middle < *__first)
3083 _BidirectionalIterator __first_cut = __first;
3084 _BidirectionalIterator __second_cut = __middle;
3085 _Distance __len11 = 0;
3086 _Distance __len22 = 0;
3087 if (__len1 > __len2)
3089 __len11 = __len1 / 2;
3096 __len22 = __len2 / 2;
3102 _BidirectionalIterator __new_middle = __first_cut;
3107 __len1 - __len11, __len2 - __len22);
3111 template<
typename _BidirectionalIterator,
typename _Distance,
3115 _BidirectionalIterator __middle,
3116 _BidirectionalIterator __last,
3117 _Distance __len1, _Distance __len2,
3120 if (__len1 == 0 || __len2 == 0)
3122 if (__len1 + __len2 == 2)
3124 if (__comp(*__middle, *__first))
3128 _BidirectionalIterator __first_cut = __first;
3129 _BidirectionalIterator __second_cut = __middle;
3130 _Distance __len11 = 0;
3131 _Distance __len22 = 0;
3132 if (__len1 > __len2)
3134 __len11 = __len1 / 2;
3142 __len22 = __len2 / 2;
3149 _BidirectionalIterator __new_middle = __first_cut;
3152 __len11, __len22, __comp);
3154 __len1 - __len11, __len2 - __len22, __comp);
3175 template<
typename _B
idirectionalIterator>
3177 inplace_merge(_BidirectionalIterator __first,
3178 _BidirectionalIterator __middle,
3179 _BidirectionalIterator __last)
3181 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3183 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3187 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3188 _BidirectionalIterator>)
3189 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3190 __glibcxx_requires_sorted(__first, __middle);
3191 __glibcxx_requires_sorted(__middle, __last);
3193 if (__first == __middle || __middle == __last)
3201 if (__buf.
begin() == 0)
3205 __buf.
begin(), _DistanceType(__buf.
size()));
3230 template<
typename _B
idirectionalIterator,
typename _Compare>
3232 inplace_merge(_BidirectionalIterator __first,
3233 _BidirectionalIterator __middle,
3234 _BidirectionalIterator __last,
3237 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3239 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3243 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3244 _BidirectionalIterator>)
3245 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3246 _ValueType, _ValueType>)
3247 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3248 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3250 if (__first == __middle || __middle == __last)
3253 const _DistanceType __len1 =
std::distance(__first, __middle);
3254 const _DistanceType __len2 =
std::distance(__middle, __last);
3258 if (__buf.
begin() == 0)
3263 __buf.
begin(), _DistanceType(__buf.
size()),
3269 template<
typename _InputIterator1,
typename _InputIterator2,
3270 typename _OutputIterator>
3273 _InputIterator2 __first2, _InputIterator2 __last2,
3274 _OutputIterator __result)
3276 while (__first1 != __last1 && __first2 != __last2)
3278 if (*__first2 < *__first1)
3280 *__result = _GLIBCXX_MOVE(*__first2);
3285 *__result = _GLIBCXX_MOVE(*__first1);
3290 return _GLIBCXX_MOVE3(__first2, __last2,
3291 _GLIBCXX_MOVE3(__first1, __last1,
3296 template<
typename _InputIterator1,
typename _InputIterator2,
3297 typename _OutputIterator,
typename _Compare>
3300 _InputIterator2 __first2, _InputIterator2 __last2,
3301 _OutputIterator __result, _Compare __comp)
3303 while (__first1 != __last1 && __first2 != __last2)
3305 if (__comp(*__first2, *__first1))
3307 *__result = _GLIBCXX_MOVE(*__first2);
3312 *__result = _GLIBCXX_MOVE(*__first1);
3317 return _GLIBCXX_MOVE3(__first2, __last2,
3318 _GLIBCXX_MOVE3(__first1, __last1,
3322 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
3325 __merge_sort_loop(_RandomAccessIterator1 __first,
3326 _RandomAccessIterator1 __last,
3327 _RandomAccessIterator2 __result,
3328 _Distance __step_size)
3330 const _Distance __two_step = 2 * __step_size;
3332 while (__last - __first >= __two_step)
3335 __first + __step_size,
3336 __first + __two_step, __result);
3337 __first += __two_step;
3340 __step_size =
std::min(_Distance(__last - __first), __step_size);
3342 __first + __step_size, __last, __result);
3345 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
3346 typename _Distance,
typename _Compare>
3348 __merge_sort_loop(_RandomAccessIterator1 __first,
3349 _RandomAccessIterator1 __last,
3350 _RandomAccessIterator2 __result, _Distance __step_size,
3353 const _Distance __two_step = 2 * __step_size;
3355 while (__last - __first >= __two_step)
3358 __first + __step_size,
3359 __first + __two_step,
3361 __first += __two_step;
3363 __step_size =
std::min(_Distance(__last - __first), __step_size);
3366 __first + __step_size, __last, __result, __comp);
3369 template<
typename _RandomAccessIterator,
typename _Distance>
3371 __chunk_insertion_sort(_RandomAccessIterator __first,
3372 _RandomAccessIterator __last,
3373 _Distance __chunk_size)
3375 while (__last - __first >= __chunk_size)
3378 __first += __chunk_size;
3383 template<
typename _RandomAccessIterator,
typename _Distance,
3386 __chunk_insertion_sort(_RandomAccessIterator __first,
3387 _RandomAccessIterator __last,
3388 _Distance __chunk_size, _Compare __comp)
3390 while (__last - __first >= __chunk_size)
3393 __first += __chunk_size;
3398 enum { _S_chunk_size = 7 };
3400 template<
typename _RandomAccessIterator,
typename _Po
inter>
3402 __merge_sort_with_buffer(_RandomAccessIterator __first,
3403 _RandomAccessIterator __last,
3406 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3409 const _Distance __len = __last - __first;
3410 const _Pointer __buffer_last = __buffer + __len;
3412 _Distance __step_size = _S_chunk_size;
3413 std::__chunk_insertion_sort(__first, __last, __step_size);
3415 while (__step_size < __len)
3417 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3419 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3424 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
3426 __merge_sort_with_buffer(_RandomAccessIterator __first,
3427 _RandomAccessIterator __last,
3428 _Pointer __buffer, _Compare __comp)
3430 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3433 const _Distance __len = __last - __first;
3434 const _Pointer __buffer_last = __buffer + __len;
3436 _Distance __step_size = _S_chunk_size;
3437 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3439 while (__step_size < __len)
3441 std::__merge_sort_loop(__first, __last, __buffer,
3442 __step_size, __comp);
3444 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3445 __step_size, __comp);
3450 template<
typename _RandomAccessIterator,
typename _Pointer,
3453 __stable_sort_adaptive(_RandomAccessIterator __first,
3454 _RandomAccessIterator __last,
3455 _Pointer __buffer, _Distance __buffer_size)
3457 const _Distance __len = (__last - __first + 1) / 2;
3458 const _RandomAccessIterator __middle = __first + __len;
3459 if (__len > __buffer_size)
3461 std::__stable_sort_adaptive(__first, __middle,
3462 __buffer, __buffer_size);
3463 std::__stable_sort_adaptive(__middle, __last,
3464 __buffer, __buffer_size);
3468 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3469 std::__merge_sort_with_buffer(__middle, __last, __buffer);
3472 _Distance(__middle - __first),
3473 _Distance(__last - __middle),
3474 __buffer, __buffer_size);
3477 template<
typename _RandomAccessIterator,
typename _Pointer,
3478 typename _Distance,
typename _Compare>
3480 __stable_sort_adaptive(_RandomAccessIterator __first,
3481 _RandomAccessIterator __last,
3482 _Pointer __buffer, _Distance __buffer_size,
3485 const _Distance __len = (__last - __first + 1) / 2;
3486 const _RandomAccessIterator __middle = __first + __len;
3487 if (__len > __buffer_size)
3489 std::__stable_sort_adaptive(__first, __middle, __buffer,
3490 __buffer_size, __comp);
3491 std::__stable_sort_adaptive(__middle, __last, __buffer,
3492 __buffer_size, __comp);
3496 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3497 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3500 _Distance(__middle - __first),
3501 _Distance(__last - __middle),
3502 __buffer, __buffer_size,
3507 template<
typename _RandomAccessIterator>
3510 _RandomAccessIterator __last)
3512 if (__last - __first < 15)
3517 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3526 template<
typename _RandomAccessIterator,
typename _Compare>
3529 _RandomAccessIterator __last, _Compare __comp)
3531 if (__last - __first < 15)
3536 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3570 template<
typename _InputIterator1,
typename _InputIterator2>
3572 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3573 _InputIterator2 __first2, _InputIterator2 __last2)
3575 typedef typename iterator_traits<_InputIterator1>::value_type
3577 typedef typename iterator_traits<_InputIterator2>::value_type
3581 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3582 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3583 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3584 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3585 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3586 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3588 while (__first1 != __last1 && __first2 != __last2)
3589 if (*__first2 < *__first1)
3591 else if(*__first1 < *__first2)
3594 ++__first1, ++__first2;
3596 return __first2 == __last2;
3620 template<
typename _InputIterator1,
typename _InputIterator2,
3623 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3624 _InputIterator2 __first2, _InputIterator2 __last2,
3627 typedef typename iterator_traits<_InputIterator1>::value_type
3629 typedef typename iterator_traits<_InputIterator2>::value_type
3633 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3634 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3635 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3636 _ValueType1, _ValueType2>)
3637 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3638 _ValueType2, _ValueType1>)
3639 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3640 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3642 while (__first1 != __last1 && __first2 != __last2)
3643 if (__comp(*__first2, *__first1))
3645 else if(__comp(*__first1, *__first2))
3648 ++__first1, ++__first2;
3650 return __first2 == __last2;
3675 template<
typename _B
idirectionalIterator>
3677 next_permutation(_BidirectionalIterator __first,
3678 _BidirectionalIterator __last)
3681 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3682 _BidirectionalIterator>)
3683 __glibcxx_function_requires(_LessThanComparableConcept<
3684 typename iterator_traits<_BidirectionalIterator>::value_type>)
3685 __glibcxx_requires_valid_range(__first, __last);
3687 if (__first == __last)
3689 _BidirectionalIterator __i = __first;
3698 _BidirectionalIterator __ii = __i;
3702 _BidirectionalIterator __j = __last;
3703 while (!(*__i < *--__j))
3732 template<
typename _B
idirectionalIterator,
typename _Compare>
3734 next_permutation(_BidirectionalIterator __first,
3735 _BidirectionalIterator __last, _Compare __comp)
3738 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3739 _BidirectionalIterator>)
3740 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3741 typename iterator_traits<_BidirectionalIterator>::value_type,
3742 typename iterator_traits<_BidirectionalIterator>::value_type>)
3743 __glibcxx_requires_valid_range(__first, __last);
3745 if (__first == __last)
3747 _BidirectionalIterator __i = __first;
3756 _BidirectionalIterator __ii = __i;
3758 if (__comp(*__i, *__ii))
3760 _BidirectionalIterator __j = __last;
3761 while (!
bool(__comp(*__i, *--__j)))
3788 template<
typename _B
idirectionalIterator>
3790 prev_permutation(_BidirectionalIterator __first,
3791 _BidirectionalIterator __last)
3794 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3795 _BidirectionalIterator>)
3796 __glibcxx_function_requires(_LessThanComparableConcept<
3797 typename iterator_traits<_BidirectionalIterator>::value_type>)
3798 __glibcxx_requires_valid_range(__first, __last);
3800 if (__first == __last)
3802 _BidirectionalIterator __i = __first;
3811 _BidirectionalIterator __ii = __i;
3815 _BidirectionalIterator __j = __last;
3816 while (!(*--__j < *__i))
3845 template<
typename _B
idirectionalIterator,
typename _Compare>
3847 prev_permutation(_BidirectionalIterator __first,
3848 _BidirectionalIterator __last, _Compare __comp)
3851 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3852 _BidirectionalIterator>)
3853 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3854 typename iterator_traits<_BidirectionalIterator>::value_type,
3855 typename iterator_traits<_BidirectionalIterator>::value_type>)
3856 __glibcxx_requires_valid_range(__first, __last);
3858 if (__first == __last)
3860 _BidirectionalIterator __i = __first;
3869 _BidirectionalIterator __ii = __i;
3871 if (__comp(*__ii, *__i))
3873 _BidirectionalIterator __j = __last;
3874 while (!
bool(__comp(*--__j, *__i)))
3905 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3907 replace_copy(_InputIterator __first, _InputIterator __last,
3908 _OutputIterator __result,
3909 const _Tp& __old_value,
const _Tp& __new_value)
3912 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3913 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3914 typename iterator_traits<_InputIterator>::value_type>)
3915 __glibcxx_function_requires(_EqualOpConcept<
3916 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3917 __glibcxx_requires_valid_range(__first, __last);
3919 for (; __first != __last; ++__first, ++__result)
3920 if (*__first == __old_value)
3921 *__result = __new_value;
3923 *__result = *__first;
3942 template<
typename _InputIterator,
typename _OutputIterator,
3943 typename _Predicate,
typename _Tp>
3945 replace_copy_if(_InputIterator __first, _InputIterator __last,
3946 _OutputIterator __result,
3947 _Predicate __pred,
const _Tp& __new_value)
3950 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3951 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3952 typename iterator_traits<_InputIterator>::value_type>)
3953 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3954 typename iterator_traits<_InputIterator>::value_type>)
3955 __glibcxx_requires_valid_range(__first, __last);
3957 for (; __first != __last; ++__first, ++__result)
3958 if (__pred(*__first))
3959 *__result = __new_value;
3961 *__result = *__first;
3965 #if __cplusplus >= 201103L
3973 template<
typename _ForwardIterator>
3975 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3987 template<
typename _ForwardIterator,
typename _Compare>
3989 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
4001 template<
typename _ForwardIterator>
4003 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
4006 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4007 __glibcxx_function_requires(_LessThanComparableConcept<
4008 typename iterator_traits<_ForwardIterator>::value_type>)
4009 __glibcxx_requires_valid_range(__first, __last);
4011 if (__first == __last)
4014 _ForwardIterator __next = __first;
4015 for (++__next; __next != __last; __first = __next, ++__next)
4016 if (*__next < *__first)
4030 template<
typename _ForwardIterator,
typename _Compare>
4032 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
4036 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4037 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4038 typename iterator_traits<_ForwardIterator>::value_type,
4039 typename iterator_traits<_ForwardIterator>::value_type>)
4040 __glibcxx_requires_valid_range(__first, __last);
4042 if (__first == __last)
4045 _ForwardIterator __next = __first;
4046 for (++__next; __next != __last; __first = __next, ++__next)
4047 if (__comp(*__next, *__first))
4060 template<
typename _Tp>
4061 inline pair<const _Tp&, const _Tp&>
4065 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4067 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
4080 template<
typename _Tp,
typename _Compare>
4081 inline pair<const _Tp&, const _Tp&>
4082 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
4099 template<
typename _ForwardIterator>
4100 pair<_ForwardIterator, _ForwardIterator>
4101 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4104 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4105 __glibcxx_function_requires(_LessThanComparableConcept<
4106 typename iterator_traits<_ForwardIterator>::value_type>)
4107 __glibcxx_requires_valid_range(__first, __last);
4109 _ForwardIterator __next = __first;
4110 if (__first == __last
4111 || ++__next == __last)
4114 _ForwardIterator __min, __max;
4115 if (*__next < *__first)
4129 while (__first != __last)
4132 if (++__next == __last)
4134 if (*__first < *__min)
4136 else if (!(*__first < *__max))
4141 if (*__next < *__first)
4143 if (*__next < *__min)
4145 if (!(*__first < *__max))
4150 if (*__first < *__min)
4152 if (!(*__next < *__max))
4175 template<
typename _ForwardIterator,
typename _Compare>
4176 pair<_ForwardIterator, _ForwardIterator>
4177 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4181 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4182 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4183 typename iterator_traits<_ForwardIterator>::value_type,
4184 typename iterator_traits<_ForwardIterator>::value_type>)
4185 __glibcxx_requires_valid_range(__first, __last);
4187 _ForwardIterator __next = __first;
4188 if (__first == __last
4189 || ++__next == __last)
4192 _ForwardIterator __min, __max;
4193 if (__comp(*__next, *__first))
4207 while (__first != __last)
4210 if (++__next == __last)
4212 if (__comp(*__first, *__min))
4214 else if (!__comp(*__first, *__max))
4219 if (__comp(*__next, *__first))
4221 if (__comp(*__next, *__min))
4223 if (!__comp(*__first, *__max))
4228 if (__comp(*__first, *__min))
4230 if (!__comp(*__next, *__max))
4242 template<
typename _Tp>
4244 min(initializer_list<_Tp> __l)
4245 {
return *std::min_element(__l.begin(), __l.end()); }
4247 template<
typename _Tp,
typename _Compare>
4249 min(initializer_list<_Tp> __l, _Compare __comp)
4252 template<
typename _Tp>
4254 max(initializer_list<_Tp> __l)
4257 template<
typename _Tp,
typename _Compare>
4259 max(initializer_list<_Tp> __l, _Compare __comp)
4262 template<
typename _Tp>
4263 inline pair<_Tp, _Tp>
4264 minmax(initializer_list<_Tp> __l)
4266 pair<const _Tp*, const _Tp*> __p =
4271 template<
typename _Tp,
typename _Compare>
4272 inline pair<_Tp, _Tp>
4273 minmax(initializer_list<_Tp> __l, _Compare __comp)
4275 pair<const _Tp*, const _Tp*> __p =
4292 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4294 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4295 _ForwardIterator2 __first2)
4299 for (; __first1 != __last1; ++__first1, ++__first2)
4300 if (!(*__first1 == *__first2))
4303 if (__first1 == __last1)
4308 _ForwardIterator2 __last2 = __first2;
4310 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4312 if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
4315 auto __matches =
std::count(__first2, __last2, *__scan);
4317 ||
std::count(__scan, __last1, *__scan) != __matches)
4337 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4338 typename _BinaryPredicate>
4340 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4341 _ForwardIterator2 __first2, _BinaryPredicate __pred)
4345 for (; __first1 != __last1; ++__first1, ++__first2)
4346 if (!
bool(__pred(*__first1, *__first2)))
4349 if (__first1 == __last1)
4354 _ForwardIterator2 __last2 = __first2;
4356 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4358 using std::placeholders::_1;
4360 if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
4368 std::bind(__pred, _1, *__scan)) != __matches)
4374 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4387 template<
typename _RandomAccessIterator,
4388 typename _UniformRandomNumberGenerator>
4390 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4391 _UniformRandomNumberGenerator&& __g)
4394 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4395 _RandomAccessIterator>)
4396 __glibcxx_requires_valid_range(__first, __last);
4398 if (__first == __last)
4401 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4404 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
4406 typedef typename __distr_type::param_type __p_type;
4409 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4410 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4416 _GLIBCXX_END_NAMESPACE_VERSION
4418 _GLIBCXX_BEGIN_NAMESPACE_ALGO
4432 template<
typename _InputIterator,
typename _Function>
4434 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4437 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4438 __glibcxx_requires_valid_range(__first, __last);
4439 for (; __first != __last; ++__first)
4441 return _GLIBCXX_MOVE(__f);
4453 template<
typename _InputIterator,
typename _Tp>
4454 inline _InputIterator
4455 find(_InputIterator __first, _InputIterator __last,
4459 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4460 __glibcxx_function_requires(_EqualOpConcept<
4461 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4462 __glibcxx_requires_valid_range(__first, __last);
4477 template<
typename _InputIterator,
typename _Predicate>
4478 inline _InputIterator
4479 find_if(_InputIterator __first, _InputIterator __last,
4483 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4484 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4485 typename iterator_traits<_InputIterator>::value_type>)
4486 __glibcxx_requires_valid_range(__first, __last);
4507 template<
typename _InputIterator,
typename _ForwardIterator>
4509 find_first_of(_InputIterator __first1, _InputIterator __last1,
4510 _ForwardIterator __first2, _ForwardIterator __last2)
4513 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4514 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4515 __glibcxx_function_requires(_EqualOpConcept<
4516 typename iterator_traits<_InputIterator>::value_type,
4517 typename iterator_traits<_ForwardIterator>::value_type>)
4518 __glibcxx_requires_valid_range(__first1, __last1);
4519 __glibcxx_requires_valid_range(__first2, __last2);
4521 for (; __first1 != __last1; ++__first1)
4522 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4523 if (*__first1 == *__iter)
4547 template<
typename _InputIterator,
typename _ForwardIterator,
4548 typename _BinaryPredicate>
4550 find_first_of(_InputIterator __first1, _InputIterator __last1,
4551 _ForwardIterator __first2, _ForwardIterator __last2,
4552 _BinaryPredicate __comp)
4555 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4556 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4557 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4558 typename iterator_traits<_InputIterator>::value_type,
4559 typename iterator_traits<_ForwardIterator>::value_type>)
4560 __glibcxx_requires_valid_range(__first1, __last1);
4561 __glibcxx_requires_valid_range(__first2, __last2);
4563 for (; __first1 != __last1; ++__first1)
4564 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4565 if (__comp(*__first1, *__iter))
4579 template<
typename _ForwardIterator>
4581 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4584 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4585 __glibcxx_function_requires(_EqualityComparableConcept<
4586 typename iterator_traits<_ForwardIterator>::value_type>)
4587 __glibcxx_requires_valid_range(__first, __last);
4588 if (__first == __last)
4590 _ForwardIterator __next = __first;
4591 while(++__next != __last)
4593 if (*__first == *__next)
4611 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4613 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4614 _BinaryPredicate __binary_pred)
4617 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4618 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4619 typename iterator_traits<_ForwardIterator>::value_type,
4620 typename iterator_traits<_ForwardIterator>::value_type>)
4621 __glibcxx_requires_valid_range(__first, __last);
4622 if (__first == __last)
4624 _ForwardIterator __next = __first;
4625 while(++__next != __last)
4627 if (__binary_pred(*__first, *__next))
4643 template<
typename _InputIterator,
typename _Tp>
4644 typename iterator_traits<_InputIterator>::difference_type
4645 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4648 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4649 __glibcxx_function_requires(_EqualOpConcept<
4650 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4651 __glibcxx_requires_valid_range(__first, __last);
4652 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4653 for (; __first != __last; ++__first)
4654 if (*__first == __value)
4668 template<
typename _InputIterator,
typename _Predicate>
4669 typename iterator_traits<_InputIterator>::difference_type
4670 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4673 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4674 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4675 typename iterator_traits<_InputIterator>::value_type>)
4676 __glibcxx_requires_valid_range(__first, __last);
4677 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4678 for (; __first != __last; ++__first)
4679 if (__pred(*__first))
4710 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4712 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4713 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4716 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4717 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4718 __glibcxx_function_requires(_EqualOpConcept<
4719 typename iterator_traits<_ForwardIterator1>::value_type,
4720 typename iterator_traits<_ForwardIterator2>::value_type>)
4721 __glibcxx_requires_valid_range(__first1, __last1);
4722 __glibcxx_requires_valid_range(__first2, __last2);
4725 if (__first1 == __last1 || __first2 == __last2)
4729 _ForwardIterator2 __p1(__first2);
4730 if (++__p1 == __last2)
4731 return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4734 _ForwardIterator2 __p;
4735 _ForwardIterator1 __current = __first1;
4739 __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4740 if (__first1 == __last1)
4744 __current = __first1;
4745 if (++__current == __last1)
4748 while (*__current == *__p)
4750 if (++__p == __last2)
4752 if (++__current == __last1)
4781 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4782 typename _BinaryPredicate>
4784 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4785 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4786 _BinaryPredicate __predicate)
4789 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4790 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4791 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4792 typename iterator_traits<_ForwardIterator1>::value_type,
4793 typename iterator_traits<_ForwardIterator2>::value_type>)
4794 __glibcxx_requires_valid_range(__first1, __last1);
4795 __glibcxx_requires_valid_range(__first2, __last2);
4798 if (__first1 == __last1 || __first2 == __last2)
4802 _ForwardIterator2 __p1(__first2);
4803 if (++__p1 == __last2)
4805 while (__first1 != __last1
4806 && !
bool(__predicate(*__first1, *__first2)))
4812 _ForwardIterator2 __p;
4813 _ForwardIterator1 __current = __first1;
4817 while (__first1 != __last1
4818 && !
bool(__predicate(*__first1, *__first2)))
4820 if (__first1 == __last1)
4824 __current = __first1;
4825 if (++__current == __last1)
4828 while (__predicate(*__current, *__p))
4830 if (++__p == __last2)
4832 if (++__current == __last1)
4856 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4858 search_n(_ForwardIterator __first, _ForwardIterator __last,
4859 _Integer __count,
const _Tp& __val)
4862 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4863 __glibcxx_function_requires(_EqualOpConcept<
4864 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4865 __glibcxx_requires_valid_range(__first, __last);
4870 return _GLIBCXX_STD_A::find(__first, __last, __val);
4893 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4894 typename _BinaryPredicate>
4896 search_n(_ForwardIterator __first, _ForwardIterator __last,
4897 _Integer __count,
const _Tp& __val,
4898 _BinaryPredicate __binary_pred)
4901 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4902 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4903 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4904 __glibcxx_requires_valid_range(__first, __last);
4910 while (__first != __last && !
bool(__binary_pred(*__first, __val)))
4914 return std::__search_n(__first, __last, __count, __val, __binary_pred,
4935 template<
typename _InputIterator,
typename _OutputIterator,
4936 typename _UnaryOperation>
4938 transform(_InputIterator __first, _InputIterator __last,
4939 _OutputIterator __result, _UnaryOperation __unary_op)
4942 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4943 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4945 __typeof__(__unary_op(*__first))>)
4946 __glibcxx_requires_valid_range(__first, __last);
4948 for (; __first != __last; ++__first, ++__result)
4949 *__result = __unary_op(*__first);
4972 template<
typename _InputIterator1,
typename _InputIterator2,
4973 typename _OutputIterator,
typename _BinaryOperation>
4975 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4976 _InputIterator2 __first2, _OutputIterator __result,
4977 _BinaryOperation __binary_op)
4980 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4981 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4982 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4984 __typeof__(__binary_op(*__first1,*__first2))>)
4985 __glibcxx_requires_valid_range(__first1, __last1);
4987 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4988 *__result = __binary_op(*__first1, *__first2);
5005 template<
typename _ForwardIterator,
typename _Tp>
5007 replace(_ForwardIterator __first, _ForwardIterator __last,
5008 const _Tp& __old_value,
const _Tp& __new_value)
5011 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5013 __glibcxx_function_requires(_EqualOpConcept<
5014 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
5015 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5016 typename iterator_traits<_ForwardIterator>::value_type>)
5017 __glibcxx_requires_valid_range(__first, __last);
5019 for (; __first != __last; ++__first)
5020 if (*__first == __old_value)
5021 *__first = __new_value;
5037 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
5039 replace_if(_ForwardIterator __first, _ForwardIterator __last,
5040 _Predicate __pred,
const _Tp& __new_value)
5043 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5045 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
5046 typename iterator_traits<_ForwardIterator>::value_type>)
5047 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5048 typename iterator_traits<_ForwardIterator>::value_type>)
5049 __glibcxx_requires_valid_range(__first, __last);
5051 for (; __first != __last; ++__first)
5052 if (__pred(*__first))
5053 *__first = __new_value;
5069 template<
typename _ForwardIterator,
typename _Generator>
5071 generate(_ForwardIterator __first, _ForwardIterator __last,
5075 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5076 __glibcxx_function_requires(_GeneratorConcept<_Generator,
5077 typename iterator_traits<_ForwardIterator>::value_type>)
5078 __glibcxx_requires_valid_range(__first, __last);
5080 for (; __first != __last; ++__first)
5100 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
5102 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5105 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5107 __typeof__(__gen())>)
5109 for (__decltype(__n + 0) __niter = __n;
5110 __niter > 0; --__niter, ++__first)
5137 template<
typename _InputIterator,
typename _OutputIterator>
5138 inline _OutputIterator
5139 unique_copy(_InputIterator __first, _InputIterator __last,
5140 _OutputIterator __result)
5143 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5144 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5145 typename iterator_traits<_InputIterator>::value_type>)
5146 __glibcxx_function_requires(_EqualityComparableConcept<
5147 typename iterator_traits<_InputIterator>::value_type>)
5148 __glibcxx_requires_valid_range(__first, __last);
5150 if (__first == __last)
5176 template<
typename _InputIterator,
typename _OutputIterator,
5177 typename _BinaryPredicate>
5178 inline _OutputIterator
5179 unique_copy(_InputIterator __first, _InputIterator __last,
5180 _OutputIterator __result,
5181 _BinaryPredicate __binary_pred)
5184 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5185 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5186 typename iterator_traits<_InputIterator>::value_type>)
5187 __glibcxx_requires_valid_range(__first, __last);
5189 if (__first == __last)
5208 template<
typename _RandomAccessIterator>
5210 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5213 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5214 _RandomAccessIterator>)
5215 __glibcxx_requires_valid_range(__first, __last);
5217 if (__first != __last)
5218 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5219 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
5236 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
5238 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5239 #
if __cplusplus >= 201103L
5240 _RandomNumberGenerator&& __rand)
5242 _RandomNumberGenerator& __rand)
5246 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5247 _RandomAccessIterator>)
5248 __glibcxx_requires_valid_range(__first, __last);
5250 if (__first == __last)
5252 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5272 template<
typename _ForwardIterator,
typename _Predicate>
5273 inline _ForwardIterator
5274 partition(_ForwardIterator __first, _ForwardIterator __last,
5278 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5280 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5281 typename iterator_traits<_ForwardIterator>::value_type>)
5282 __glibcxx_requires_valid_range(__first, __last);
5306 template<
typename _RandomAccessIterator>
5308 partial_sort(_RandomAccessIterator __first,
5309 _RandomAccessIterator __middle,
5310 _RandomAccessIterator __last)
5312 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5316 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5317 _RandomAccessIterator>)
5318 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5319 __glibcxx_requires_valid_range(__first, __middle);
5320 __glibcxx_requires_valid_range(__middle, __last);
5345 template<
typename _RandomAccessIterator,
typename _Compare>
5347 partial_sort(_RandomAccessIterator __first,
5348 _RandomAccessIterator __middle,
5349 _RandomAccessIterator __last,
5352 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5356 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5357 _RandomAccessIterator>)
5358 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5359 _ValueType, _ValueType>)
5360 __glibcxx_requires_valid_range(__first, __middle);
5361 __glibcxx_requires_valid_range(__middle, __last);
5382 template<
typename _RandomAccessIterator>
5384 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5385 _RandomAccessIterator __last)
5387 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5391 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5392 _RandomAccessIterator>)
5393 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5394 __glibcxx_requires_valid_range(__first, __nth);
5395 __glibcxx_requires_valid_range(__nth, __last);
5397 if (__first == __last || __nth == __last)
5400 std::__introselect(__first, __nth, __last,
5421 template<
typename _RandomAccessIterator,
typename _Compare>
5423 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5424 _RandomAccessIterator __last, _Compare __comp)
5426 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5430 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5431 _RandomAccessIterator>)
5432 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5433 _ValueType, _ValueType>)
5434 __glibcxx_requires_valid_range(__first, __nth);
5435 __glibcxx_requires_valid_range(__nth, __last);
5437 if (__first == __last || __nth == __last)
5440 std::__introselect(__first, __nth, __last,
5441 std::__lg(__last - __first) * 2, __comp);
5459 template<
typename _RandomAccessIterator>
5461 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5463 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5467 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5468 _RandomAccessIterator>)
5469 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5470 __glibcxx_requires_valid_range(__first, __last);
5472 if (__first != __last)
5495 template<
typename _RandomAccessIterator,
typename _Compare>
5497 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5500 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5504 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5505 _RandomAccessIterator>)
5506 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5508 __glibcxx_requires_valid_range(__first, __last);
5510 if (__first != __last)
5513 std::__lg(__last - __first) * 2, __comp);
5537 template<
typename _InputIterator1,
typename _InputIterator2,
5538 typename _OutputIterator>
5540 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5541 _InputIterator2 __first2, _InputIterator2 __last2,
5542 _OutputIterator __result)
5544 typedef typename iterator_traits<_InputIterator1>::value_type
5546 typedef typename iterator_traits<_InputIterator2>::value_type
5550 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5551 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5552 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5554 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5556 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5557 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5558 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5560 while (__first1 != __last1 && __first2 != __last2)
5562 if (*__first2 < *__first1)
5564 *__result = *__first2;
5569 *__result = *__first1;
5574 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5601 template<
typename _InputIterator1,
typename _InputIterator2,
5602 typename _OutputIterator,
typename _Compare>
5604 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5605 _InputIterator2 __first2, _InputIterator2 __last2,
5606 _OutputIterator __result, _Compare __comp)
5608 typedef typename iterator_traits<_InputIterator1>::value_type
5610 typedef typename iterator_traits<_InputIterator2>::value_type
5614 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5615 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5616 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5618 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5620 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5621 _ValueType2, _ValueType1>)
5622 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5623 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5625 while (__first1 != __last1 && __first2 != __last2)
5627 if (__comp(*__first2, *__first1))
5629 *__result = *__first2;
5634 *__result = *__first1;
5639 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5661 template<
typename _RandomAccessIterator>
5663 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5665 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5667 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5671 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5672 _RandomAccessIterator>)
5673 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5674 __glibcxx_requires_valid_range(__first, __last);
5678 if (__buf.
begin() == 0)
5681 std::__stable_sort_adaptive(__first, __last, __buf.
begin(),
5682 _DistanceType(__buf.
size()));
5703 template<
typename _RandomAccessIterator,
typename _Compare>
5705 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5708 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5710 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5714 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5715 _RandomAccessIterator>)
5716 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5719 __glibcxx_requires_valid_range(__first, __last);
5723 if (__buf.
begin() == 0)
5726 std::__stable_sort_adaptive(__first, __last, __buf.
begin(),
5727 _DistanceType(__buf.
size()), __comp);
5749 template<
typename _InputIterator1,
typename _InputIterator2,
5750 typename _OutputIterator>
5752 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5753 _InputIterator2 __first2, _InputIterator2 __last2,
5754 _OutputIterator __result)
5756 typedef typename iterator_traits<_InputIterator1>::value_type
5758 typedef typename iterator_traits<_InputIterator2>::value_type
5762 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5763 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5764 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5766 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5768 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5769 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5770 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5771 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5773 while (__first1 != __last1 && __first2 != __last2)
5775 if (*__first1 < *__first2)
5777 *__result = *__first1;
5780 else if (*__first2 < *__first1)
5782 *__result = *__first2;
5787 *__result = *__first1;
5793 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5816 template<
typename _InputIterator1,
typename _InputIterator2,
5817 typename _OutputIterator,
typename _Compare>
5819 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5820 _InputIterator2 __first2, _InputIterator2 __last2,
5821 _OutputIterator __result, _Compare __comp)
5823 typedef typename iterator_traits<_InputIterator1>::value_type
5825 typedef typename iterator_traits<_InputIterator2>::value_type
5829 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5830 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5831 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5833 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5835 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5836 _ValueType1, _ValueType2>)
5837 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5838 _ValueType2, _ValueType1>)
5839 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5840 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5842 while (__first1 != __last1 && __first2 != __last2)
5844 if (__comp(*__first1, *__first2))
5846 *__result = *__first1;
5849 else if (__comp(*__first2, *__first1))
5851 *__result = *__first2;
5856 *__result = *__first1;
5862 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5883 template<
typename _InputIterator1,
typename _InputIterator2,
5884 typename _OutputIterator>
5886 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5887 _InputIterator2 __first2, _InputIterator2 __last2,
5888 _OutputIterator __result)
5890 typedef typename iterator_traits<_InputIterator1>::value_type
5892 typedef typename iterator_traits<_InputIterator2>::value_type
5896 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5897 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5898 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5900 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5901 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5902 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5903 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5905 while (__first1 != __last1 && __first2 != __last2)
5906 if (*__first1 < *__first2)
5908 else if (*__first2 < *__first1)
5912 *__result = *__first1;
5940 template<
typename _InputIterator1,
typename _InputIterator2,
5941 typename _OutputIterator,
typename _Compare>
5943 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5944 _InputIterator2 __first2, _InputIterator2 __last2,
5945 _OutputIterator __result, _Compare __comp)
5947 typedef typename iterator_traits<_InputIterator1>::value_type
5949 typedef typename iterator_traits<_InputIterator2>::value_type
5953 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5954 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5955 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5957 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5958 _ValueType1, _ValueType2>)
5959 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5960 _ValueType2, _ValueType1>)
5961 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5962 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5964 while (__first1 != __last1 && __first2 != __last2)
5965 if (__comp(*__first1, *__first2))
5967 else if (__comp(*__first2, *__first1))
5971 *__result = *__first1;
5998 template<
typename _InputIterator1,
typename _InputIterator2,
5999 typename _OutputIterator>
6001 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6002 _InputIterator2 __first2, _InputIterator2 __last2,
6003 _OutputIterator __result)
6005 typedef typename iterator_traits<_InputIterator1>::value_type
6007 typedef typename iterator_traits<_InputIterator2>::value_type
6011 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6012 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6013 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6015 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6016 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6017 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6018 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6020 while (__first1 != __last1 && __first2 != __last2)
6021 if (*__first1 < *__first2)
6023 *__result = *__first1;
6027 else if (*__first2 < *__first1)
6034 return std::copy(__first1, __last1, __result);
6059 template<
typename _InputIterator1,
typename _InputIterator2,
6060 typename _OutputIterator,
typename _Compare>
6062 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6063 _InputIterator2 __first2, _InputIterator2 __last2,
6064 _OutputIterator __result, _Compare __comp)
6066 typedef typename iterator_traits<_InputIterator1>::value_type
6068 typedef typename iterator_traits<_InputIterator2>::value_type
6072 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6073 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6074 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6076 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6077 _ValueType1, _ValueType2>)
6078 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6079 _ValueType2, _ValueType1>)
6080 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6081 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6083 while (__first1 != __last1 && __first2 != __last2)
6084 if (__comp(*__first1, *__first2))
6086 *__result = *__first1;
6090 else if (__comp(*__first2, *__first1))
6097 return std::copy(__first1, __last1, __result);
6117 template<
typename _InputIterator1,
typename _InputIterator2,
6118 typename _OutputIterator>
6120 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6121 _InputIterator2 __first2, _InputIterator2 __last2,
6122 _OutputIterator __result)
6124 typedef typename iterator_traits<_InputIterator1>::value_type
6126 typedef typename iterator_traits<_InputIterator2>::value_type
6130 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6131 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6132 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6134 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6136 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6137 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6138 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6139 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6141 while (__first1 != __last1 && __first2 != __last2)
6142 if (*__first1 < *__first2)
6144 *__result = *__first1;
6148 else if (*__first2 < *__first1)
6150 *__result = *__first2;
6159 return std::copy(__first2, __last2, std::copy(__first1,
6160 __last1, __result));
6183 template<
typename _InputIterator1,
typename _InputIterator2,
6184 typename _OutputIterator,
typename _Compare>
6186 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6187 _InputIterator2 __first2, _InputIterator2 __last2,
6188 _OutputIterator __result,
6191 typedef typename iterator_traits<_InputIterator1>::value_type
6193 typedef typename iterator_traits<_InputIterator2>::value_type
6197 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6198 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6199 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6201 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6203 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6204 _ValueType1, _ValueType2>)
6205 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6206 _ValueType2, _ValueType1>)
6207 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6208 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6210 while (__first1 != __last1 && __first2 != __last2)
6211 if (__comp(*__first1, *__first2))
6213 *__result = *__first1;
6217 else if (__comp(*__first2, *__first1))
6219 *__result = *__first2;
6228 return std::copy(__first2, __last2,
6229 std::copy(__first1, __last1, __result));
6240 template<
typename _ForwardIterator>
6242 min_element(_ForwardIterator __first, _ForwardIterator __last)
6245 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6246 __glibcxx_function_requires(_LessThanComparableConcept<
6247 typename iterator_traits<_ForwardIterator>::value_type>)
6248 __glibcxx_requires_valid_range(__first, __last);
6250 if (__first == __last)
6252 _ForwardIterator __result = __first;
6253 while (++__first != __last)
6254 if (*__first < *__result)
6268 template<
typename _ForwardIterator,
typename _Compare>
6270 min_element(_ForwardIterator __first, _ForwardIterator __last,
6274 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6275 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6276 typename iterator_traits<_ForwardIterator>::value_type,
6277 typename iterator_traits<_ForwardIterator>::value_type>)
6278 __glibcxx_requires_valid_range(__first, __last);
6280 if (__first == __last)
6282 _ForwardIterator __result = __first;
6283 while (++__first != __last)
6284 if (__comp(*__first, *__result))
6296 template<
typename _ForwardIterator>
6298 max_element(_ForwardIterator __first, _ForwardIterator __last)
6301 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6302 __glibcxx_function_requires(_LessThanComparableConcept<
6303 typename iterator_traits<_ForwardIterator>::value_type>)
6304 __glibcxx_requires_valid_range(__first, __last);
6306 if (__first == __last)
6308 _ForwardIterator __result = __first;
6309 while (++__first != __last)
6310 if (*__result < *__first)
6324 template<
typename _ForwardIterator,
typename _Compare>
6326 max_element(_ForwardIterator __first, _ForwardIterator __last,
6330 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6331 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6332 typename iterator_traits<_ForwardIterator>::value_type,
6333 typename iterator_traits<_ForwardIterator>::value_type>)
6334 __glibcxx_requires_valid_range(__first, __last);
6336 if (__first == __last)
return __first;
6337 _ForwardIterator __result = __first;
6338 while (++__first != __last)
6339 if (__comp(*__result, *__first))
6344 _GLIBCXX_END_NAMESPACE_ALGO