66 #ifdef __GXX_EXPERIMENTAL_CXX0X__
73 namespace std _GLIBCXX_VISIBILITY(default)
75 _GLIBCXX_BEGIN_NAMESPACE_VERSION
78 template<
typename _Iterator>
83 __glibcxx_function_requires(_LessThanComparableConcept<
84 typename iterator_traits<_Iterator>::value_type>)
102 template<
typename _Iterator,
typename _Compare>
108 __glibcxx_function_requires(_BinaryFunctionConcept<_Compare,
bool,
109 typename iterator_traits<_Iterator>::value_type,
110 typename iterator_traits<_Iterator>::value_type>)
112 if (__comp(*__a, *__b))
114 if (__comp(*__b, *__c))
116 else if (__comp(*__a, *__c))
119 else if (__comp(*__a, *__c))
121 else if (__comp(*__b, *__c))
130 template<
typename _InputIterator,
typename _Tp>
131 inline _InputIterator
132 __find(_InputIterator __first, _InputIterator __last,
135 while (__first != __last && !(*__first == __val))
141 template<
typename _InputIterator,
typename _Predicate>
142 inline _InputIterator
143 __find_if(_InputIterator __first, _InputIterator __last,
146 while (__first != __last && !
bool(__pred(*__first)))
152 template<
typename _RandomAccessIterator,
typename _Tp>
153 _RandomAccessIterator
154 __find(_RandomAccessIterator __first, _RandomAccessIterator __last,
157 typename iterator_traits<_RandomAccessIterator>::difference_type
158 __trip_count = (__last - __first) >> 2;
160 for (; __trip_count > 0; --__trip_count)
162 if (*__first == __val)
166 if (*__first == __val)
170 if (*__first == __val)
174 if (*__first == __val)
179 switch (__last - __first)
182 if (*__first == __val)
186 if (*__first == __val)
190 if (*__first == __val)
200 template<
typename _RandomAccessIterator,
typename _Predicate>
201 _RandomAccessIterator
202 __find_if(_RandomAccessIterator __first, _RandomAccessIterator __last,
205 typename iterator_traits<_RandomAccessIterator>::difference_type
206 __trip_count = (__last - __first) >> 2;
208 for (; __trip_count > 0; --__trip_count)
210 if (__pred(*__first))
214 if (__pred(*__first))
218 if (__pred(*__first))
222 if (__pred(*__first))
227 switch (__last - __first)
230 if (__pred(*__first))
234 if (__pred(*__first))
238 if (__pred(*__first))
247 #ifdef __GXX_EXPERIMENTAL_CXX0X__
249 template<
typename _InputIterator,
typename _Predicate>
250 inline _InputIterator
254 while (__first != __last &&
bool(__pred(*__first)))
260 template<
typename _RandomAccessIterator,
typename _Predicate>
261 _RandomAccessIterator
265 typename iterator_traits<_RandomAccessIterator>::difference_type
266 __trip_count = (__last - __first) >> 2;
268 for (; __trip_count > 0; --__trip_count)
270 if (!
bool(__pred(*__first)))
274 if (!
bool(__pred(*__first)))
278 if (!
bool(__pred(*__first)))
282 if (!
bool(__pred(*__first)))
287 switch (__last - __first)
290 if (!
bool(__pred(*__first)))
294 if (!
bool(__pred(*__first)))
298 if (!
bool(__pred(*__first)))
326 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
328 __search_n(_ForwardIterator __first, _ForwardIterator __last,
329 _Integer __count,
const _Tp& __val,
332 __first = _GLIBCXX_STD_A::find(__first, __last, __val);
333 while (__first != __last)
335 typename iterator_traits<_ForwardIterator>::difference_type
337 _ForwardIterator __i = __first;
339 while (__i != __last && __n != 1 && *__i == __val)
348 __first = _GLIBCXX_STD_A::find(++__i, __last, __val);
358 template<
typename _RandomAccessIter,
typename _Integer,
typename _Tp>
360 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
361 _Integer __count,
const _Tp& __val,
365 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
368 _DistanceType __tailSize = __last - __first;
369 const _DistanceType __pattSize = __count;
371 if (__tailSize < __pattSize)
374 const _DistanceType __skipOffset = __pattSize - 1;
375 _RandomAccessIter __lookAhead = __first + __skipOffset;
376 __tailSize -= __pattSize;
382 while (!(*__lookAhead == __val))
384 if (__tailSize < __pattSize)
386 __lookAhead += __pattSize;
387 __tailSize -= __pattSize;
389 _DistanceType __remainder = __skipOffset;
390 for (_RandomAccessIter __backTrack = __lookAhead - 1;
391 *__backTrack == __val; --__backTrack)
393 if (--__remainder == 0)
394 return (__lookAhead - __skipOffset);
396 if (__remainder > __tailSize)
398 __lookAhead += __remainder;
399 __tailSize -= __remainder;
411 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
412 typename _BinaryPredicate>
414 __search_n(_ForwardIterator __first, _ForwardIterator __last,
415 _Integer __count,
const _Tp& __val,
418 while (__first != __last && !
bool(__binary_pred(*__first, __val)))
421 while (__first != __last)
423 typename iterator_traits<_ForwardIterator>::difference_type
425 _ForwardIterator __i = __first;
427 while (__i != __last && __n != 1 &&
bool(__binary_pred(*__i, __val)))
437 while (__first != __last
438 && !
bool(__binary_pred(*__first, __val)))
450 template<
typename _RandomAccessIter,
typename _Integer,
typename _Tp,
451 typename _BinaryPredicate>
453 __search_n(_RandomAccessIter __first, _RandomAccessIter __last,
454 _Integer __count,
const _Tp& __val,
458 typedef typename std::iterator_traits<_RandomAccessIter>::difference_type
461 _DistanceType __tailSize = __last - __first;
462 const _DistanceType __pattSize = __count;
464 if (__tailSize < __pattSize)
467 const _DistanceType __skipOffset = __pattSize - 1;
468 _RandomAccessIter __lookAhead = __first + __skipOffset;
469 __tailSize -= __pattSize;
475 while (!
bool(__binary_pred(*__lookAhead, __val)))
477 if (__tailSize < __pattSize)
479 __lookAhead += __pattSize;
480 __tailSize -= __pattSize;
482 _DistanceType __remainder = __skipOffset;
483 for (_RandomAccessIter __backTrack = __lookAhead - 1;
484 __binary_pred(*__backTrack, __val); --__backTrack)
486 if (--__remainder == 0)
487 return (__lookAhead - __skipOffset);
489 if (__remainder > __tailSize)
491 __lookAhead += __remainder;
492 __tailSize -= __remainder;
497 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
499 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
500 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
501 forward_iterator_tag, forward_iterator_tag)
503 if (__first2 == __last2)
507 _ForwardIterator1 __result = __last1;
510 _ForwardIterator1 __new_result
511 = _GLIBCXX_STD_A::search(__first1, __last1, __first2, __last2);
512 if (__new_result == __last1)
516 __result = __new_result;
517 __first1 = __new_result;
524 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
525 typename _BinaryPredicate>
527 __find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
528 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
529 forward_iterator_tag, forward_iterator_tag,
530 _BinaryPredicate __comp)
532 if (__first2 == __last2)
536 _ForwardIterator1 __result = __last1;
539 _ForwardIterator1 __new_result
540 = _GLIBCXX_STD_A::search(__first1, __last1, __first2,
542 if (__new_result == __last1)
546 __result = __new_result;
547 __first1 = __new_result;
555 template<
typename _B
idirectionalIterator1,
typename _B
idirectionalIterator2>
556 _BidirectionalIterator1
557 __find_end(_BidirectionalIterator1 __first1,
558 _BidirectionalIterator1 __last1,
559 _BidirectionalIterator2 __first2,
560 _BidirectionalIterator2 __last2,
561 bidirectional_iterator_tag, bidirectional_iterator_tag)
564 __glibcxx_function_requires(_BidirectionalIteratorConcept<
565 _BidirectionalIterator1>)
566 __glibcxx_function_requires(_BidirectionalIteratorConcept<
567 _BidirectionalIterator2>)
569 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
570 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
572 _RevIterator1 __rlast1(__first1);
573 _RevIterator2 __rlast2(__first2);
574 _RevIterator1 __rresult = _GLIBCXX_STD_A::search(_RevIterator1(__last1),
576 _RevIterator2(__last2),
579 if (__rresult == __rlast1)
583 _BidirectionalIterator1 __result = __rresult.base();
589 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
590 typename _BinaryPredicate>
591 _BidirectionalIterator1
592 __find_end(_BidirectionalIterator1 __first1,
593 _BidirectionalIterator1 __last1,
594 _BidirectionalIterator2 __first2,
595 _BidirectionalIterator2 __last2,
596 bidirectional_iterator_tag, bidirectional_iterator_tag,
597 _BinaryPredicate __comp)
600 __glibcxx_function_requires(_BidirectionalIteratorConcept<
601 _BidirectionalIterator1>)
602 __glibcxx_function_requires(_BidirectionalIteratorConcept<
603 _BidirectionalIterator2>)
605 typedef reverse_iterator<_BidirectionalIterator1> _RevIterator1;
606 typedef reverse_iterator<_BidirectionalIterator2> _RevIterator2;
608 _RevIterator1 __rlast1(__first1);
609 _RevIterator2 __rlast2(__first2);
610 _RevIterator1 __rresult = std::search(_RevIterator1(__last1), __rlast1,
611 _RevIterator2(__last2), __rlast2,
614 if (__rresult == __rlast1)
618 _BidirectionalIterator1 __result = __rresult.base();
649 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
650 inline _ForwardIterator1
651 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
652 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
655 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
656 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
657 __glibcxx_function_requires(_EqualOpConcept<
658 typename iterator_traits<_ForwardIterator1>::value_type,
659 typename iterator_traits<_ForwardIterator2>::value_type>)
660 __glibcxx_requires_valid_range(__first1, __last1);
661 __glibcxx_requires_valid_range(__first2, __last2);
663 return std::__find_end(__first1, __last1, __first2, __last2,
695 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
696 typename _BinaryPredicate>
697 inline _ForwardIterator1
698 find_end(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
699 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
700 _BinaryPredicate __comp)
703 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
704 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
705 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
706 typename iterator_traits<_ForwardIterator1>::value_type,
707 typename iterator_traits<_ForwardIterator2>::value_type>)
708 __glibcxx_requires_valid_range(__first1, __last1);
709 __glibcxx_requires_valid_range(__first2, __last2);
711 return std::__find_end(__first1, __last1, __first2, __last2,
717 #ifdef __GXX_EXPERIMENTAL_CXX0X__
730 template<
typename _InputIterator,
typename _Predicate>
732 all_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
747 template<
typename _InputIterator,
typename _Predicate>
749 none_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
750 {
return __last == _GLIBCXX_STD_A::find_if(__first, __last, __pred); }
764 template<
typename _InputIterator,
typename _Predicate>
766 any_of(_InputIterator __first, _InputIterator __last, _Predicate __pred)
779 template<
typename _InputIterator,
typename _Predicate>
780 inline _InputIterator
781 find_if_not(_InputIterator __first, _InputIterator __last,
785 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
786 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
787 typename iterator_traits<_InputIterator>::value_type>)
788 __glibcxx_requires_valid_range(__first, __last);
803 template<
typename _InputIterator,
typename _Predicate>
805 is_partitioned(_InputIterator __first, _InputIterator __last,
821 template<
typename _ForwardIterator,
typename _Predicate>
823 partition_point(_ForwardIterator __first, _ForwardIterator __last,
827 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
828 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
829 typename iterator_traits<_ForwardIterator>::value_type>)
832 __glibcxx_requires_valid_range(__first, __last);
834 typedef typename iterator_traits<_ForwardIterator>::difference_type
838 _DistanceType __half;
839 _ForwardIterator __middle;
846 if (__pred(*__middle))
850 __len = __len - __half - 1;
874 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
876 remove_copy(_InputIterator __first, _InputIterator __last,
877 _OutputIterator __result,
const _Tp& __value)
880 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
881 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
882 typename iterator_traits<_InputIterator>::value_type>)
883 __glibcxx_function_requires(_EqualOpConcept<
884 typename iterator_traits<_InputIterator>::value_type, _Tp>)
885 __glibcxx_requires_valid_range(__first, __last);
887 for (; __first != __last; ++__first)
888 if (!(*__first == __value))
890 *__result = *__first;
911 template<
typename _InputIterator,
typename _OutputIterator,
914 remove_copy_if(_InputIterator __first, _InputIterator __last,
915 _OutputIterator __result, _Predicate __pred)
918 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
919 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
920 typename iterator_traits<_InputIterator>::value_type>)
921 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
922 typename iterator_traits<_InputIterator>::value_type>)
923 __glibcxx_requires_valid_range(__first, __last);
925 for (; __first != __last; ++__first)
926 if (!
bool(__pred(*__first)))
928 *__result = *__first;
934 #ifdef __GXX_EXPERIMENTAL_CXX0X__
950 template<
typename _InputIterator,
typename _OutputIterator,
953 copy_if(_InputIterator __first, _InputIterator __last,
954 _OutputIterator __result, _Predicate __pred)
957 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
958 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
959 typename iterator_traits<_InputIterator>::value_type>)
960 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
961 typename iterator_traits<_InputIterator>::value_type>)
962 __glibcxx_requires_valid_range(__first, __last);
964 for (; __first != __last; ++__first)
965 if (__pred(*__first))
967 *__result = *__first;
974 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
976 __copy_n(_InputIterator __first, _Size __n,
977 _OutputIterator __result, input_iterator_tag)
979 for (; __n > 0; --__n)
981 *__result = *__first;
988 template<
typename _RandomAccessIterator,
typename _Size,
989 typename _OutputIterator>
990 inline _OutputIterator
991 __copy_n(_RandomAccessIterator __first, _Size __n,
992 _OutputIterator __result, random_access_iterator_tag)
993 {
return std::copy(__first, __first + __n, __result); }
1008 template<
typename _InputIterator,
typename _Size,
typename _OutputIterator>
1009 inline _OutputIterator
1010 copy_n(_InputIterator __first, _Size __n, _OutputIterator __result)
1013 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1014 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1015 typename iterator_traits<_InputIterator>::value_type>)
1017 return std::__copy_n(__first, __n, __result,
1036 template<
typename _InputIterator,
typename _OutputIterator1,
1037 typename _OutputIterator2,
typename _Predicate>
1038 pair<_OutputIterator1, _OutputIterator2>
1039 partition_copy(_InputIterator __first, _InputIterator __last,
1040 _OutputIterator1 __out_true, _OutputIterator2 __out_false,
1044 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1045 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator1,
1046 typename iterator_traits<_InputIterator>::value_type>)
1047 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator2,
1048 typename iterator_traits<_InputIterator>::value_type>)
1049 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1050 typename iterator_traits<_InputIterator>::value_type>)
1051 __glibcxx_requires_valid_range(__first, __last);
1053 for (; __first != __last; ++__first)
1054 if (__pred(*__first))
1056 *__out_true = *__first;
1061 *__out_false = *__first;
1086 template<
typename _ForwardIterator,
typename _Tp>
1088 remove(_ForwardIterator __first, _ForwardIterator __last,
1092 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1094 __glibcxx_function_requires(_EqualOpConcept<
1095 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
1096 __glibcxx_requires_valid_range(__first, __last);
1098 __first = _GLIBCXX_STD_A::find(__first, __last, __value);
1099 if(__first == __last)
1101 _ForwardIterator __result = __first;
1103 for(; __first != __last; ++__first)
1104 if(!(*__first == __value))
1106 *__result = _GLIBCXX_MOVE(*__first);
1129 template<
typename _ForwardIterator,
typename _Predicate>
1131 remove_if(_ForwardIterator __first, _ForwardIterator __last,
1135 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1137 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1138 typename iterator_traits<_ForwardIterator>::value_type>)
1139 __glibcxx_requires_valid_range(__first, __last);
1141 __first = _GLIBCXX_STD_A::find_if(__first, __last, __pred);
1142 if(__first == __last)
1144 _ForwardIterator __result = __first;
1146 for(; __first != __last; ++__first)
1147 if(!
bool(__pred(*__first)))
1149 *__result = _GLIBCXX_MOVE(*__first);
1169 template<
typename _ForwardIterator>
1171 unique(_ForwardIterator __first, _ForwardIterator __last)
1174 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1176 __glibcxx_function_requires(_EqualityComparableConcept<
1177 typename iterator_traits<_ForwardIterator>::value_type>)
1178 __glibcxx_requires_valid_range(__first, __last);
1181 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last);
1182 if (__first == __last)
1186 _ForwardIterator __dest = __first;
1188 while (++__first != __last)
1189 if (!(*__dest == *__first))
1190 *++__dest = _GLIBCXX_MOVE(*__first);
1209 template<
typename _ForwardIterator,
typename _BinaryPredicate>
1211 unique(_ForwardIterator __first, _ForwardIterator __last,
1212 _BinaryPredicate __binary_pred)
1215 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1217 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1218 typename iterator_traits<_ForwardIterator>::value_type,
1219 typename iterator_traits<_ForwardIterator>::value_type>)
1220 __glibcxx_requires_valid_range(__first, __last);
1223 __first = _GLIBCXX_STD_A::adjacent_find(__first, __last, __binary_pred);
1224 if (__first == __last)
1228 _ForwardIterator __dest = __first;
1230 while (++__first != __last)
1231 if (!
bool(__binary_pred(*__dest, *__first)))
1232 *++__dest = _GLIBCXX_MOVE(*__first);
1241 template<
typename _ForwardIterator,
typename _OutputIterator>
1244 _OutputIterator __result,
1248 _ForwardIterator __next = __first;
1249 *__result = *__first;
1250 while (++__next != __last)
1251 if (!(*__first == *__next))
1254 *++__result = *__first;
1264 template<
typename _InputIterator,
typename _OutputIterator>
1267 _OutputIterator __result,
1271 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1272 *__result = __value;
1273 while (++__first != __last)
1274 if (!(__value == *__first))
1277 *++__result = __value;
1287 template<
typename _InputIterator,
typename _ForwardIterator>
1290 _ForwardIterator __result,
1294 *__result = *__first;
1295 while (++__first != __last)
1296 if (!(*__result == *__first))
1297 *++__result = *__first;
1307 template<
typename _ForwardIterator,
typename _OutputIterator,
1308 typename _BinaryPredicate>
1311 _OutputIterator __result, _BinaryPredicate __binary_pred,
1315 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1316 typename iterator_traits<_ForwardIterator>::value_type,
1317 typename iterator_traits<_ForwardIterator>::value_type>)
1319 _ForwardIterator __next = __first;
1320 *__result = *__first;
1321 while (++__next != __last)
1322 if (!
bool(__binary_pred(*__first, *__next)))
1325 *++__result = *__first;
1336 template<
typename _InputIterator,
typename _OutputIterator,
1337 typename _BinaryPredicate>
1340 _OutputIterator __result, _BinaryPredicate __binary_pred,
1344 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1345 typename iterator_traits<_InputIterator>::value_type,
1346 typename iterator_traits<_InputIterator>::value_type>)
1348 typename iterator_traits<_InputIterator>::value_type __value = *__first;
1349 *__result = __value;
1350 while (++__first != __last)
1351 if (!
bool(__binary_pred(__value, *__first)))
1354 *++__result = __value;
1365 template<
typename _InputIterator,
typename _ForwardIterator,
1366 typename _BinaryPredicate>
1369 _ForwardIterator __result, _BinaryPredicate __binary_pred,
1373 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
1374 typename iterator_traits<_ForwardIterator>::value_type,
1375 typename iterator_traits<_InputIterator>::value_type>)
1377 *__result = *__first;
1378 while (++__first != __last)
1379 if (!
bool(__binary_pred(*__result, *__first)))
1380 *++__result = *__first;
1389 template<
typename _B
idirectionalIterator>
1391 __reverse(_BidirectionalIterator __first, _BidirectionalIterator __last,
1395 if (__first == __last || __first == --__last)
1409 template<
typename _RandomAccessIterator>
1411 __reverse(_RandomAccessIterator __first, _RandomAccessIterator __last,
1414 if (__first == __last)
1417 while (__first < __last)
1437 template<
typename _B
idirectionalIterator>
1439 reverse(_BidirectionalIterator __first, _BidirectionalIterator __last)
1442 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1443 _BidirectionalIterator>)
1444 __glibcxx_requires_valid_range(__first, __last);
1464 template<
typename _B
idirectionalIterator,
typename _OutputIterator>
1466 reverse_copy(_BidirectionalIterator __first, _BidirectionalIterator __last,
1467 _OutputIterator __result)
1470 __glibcxx_function_requires(_BidirectionalIteratorConcept<
1471 _BidirectionalIterator>)
1472 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1473 typename iterator_traits<_BidirectionalIterator>::value_type>)
1474 __glibcxx_requires_valid_range(__first, __last);
1476 while (__first != __last)
1479 *__result = *__last;
1489 template<
typename _Eucl
ideanRingElement>
1490 _EuclideanRingElement
1491 __gcd(_EuclideanRingElement __m, _EuclideanRingElement __n)
1495 _EuclideanRingElement __t = __m % __n;
1503 template<
typename _ForwardIterator>
1506 _ForwardIterator __middle,
1507 _ForwardIterator __last,
1510 if (__first == __middle || __last == __middle)
1513 _ForwardIterator __first2 = __middle;
1519 if (__first == __middle)
1520 __middle = __first2;
1522 while (__first2 != __last);
1524 __first2 = __middle;
1526 while (__first2 != __last)
1531 if (__first == __middle)
1532 __middle = __first2;
1533 else if (__first2 == __last)
1534 __first2 = __middle;
1539 template<
typename _B
idirectionalIterator>
1542 _BidirectionalIterator __middle,
1543 _BidirectionalIterator __last,
1547 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
1548 _BidirectionalIterator>)
1550 if (__first == __middle || __last == __middle)
1556 while (__first != __middle && __middle != __last)
1562 if (__first == __middle)
1569 template<
typename _RandomAccessIterator>
1572 _RandomAccessIterator __middle,
1573 _RandomAccessIterator __last,
1577 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
1578 _RandomAccessIterator>)
1580 if (__first == __middle || __last == __middle)
1583 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1585 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1588 _Distance __n = __last - __first;
1589 _Distance __k = __middle - __first;
1591 if (__k == __n - __k)
1597 _RandomAccessIterator __p = __first;
1601 if (__k < __n - __k)
1603 if (__is_pod(_ValueType) && __k == 1)
1605 _ValueType __t = _GLIBCXX_MOVE(*__p);
1606 _GLIBCXX_MOVE3(__p + 1, __p + __n, __p);
1607 *(__p + __n - 1) = _GLIBCXX_MOVE(__t);
1610 _RandomAccessIterator __q = __p + __k;
1611 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1620 std::swap(__n, __k);
1626 if (__is_pod(_ValueType) && __k == 1)
1628 _ValueType __t = _GLIBCXX_MOVE(*(__p + __n - 1));
1629 _GLIBCXX_MOVE_BACKWARD3(__p, __p + __n - 1, __p + __n);
1630 *__p = _GLIBCXX_MOVE(__t);
1633 _RandomAccessIterator __q = __p + __n;
1635 for (_Distance __i = 0; __i < __n - __k; ++ __i)
1644 std::swap(__n, __k);
1668 template<
typename _ForwardIterator>
1670 rotate(_ForwardIterator __first, _ForwardIterator __middle,
1671 _ForwardIterator __last)
1674 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1676 __glibcxx_requires_valid_range(__first, __middle);
1677 __glibcxx_requires_valid_range(__middle, __last);
1679 typedef typename iterator_traits<_ForwardIterator>::iterator_category
1702 template<
typename _ForwardIterator,
typename _OutputIterator>
1704 rotate_copy(_ForwardIterator __first, _ForwardIterator __middle,
1705 _ForwardIterator __last, _OutputIterator __result)
1708 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
1709 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
1710 typename iterator_traits<_ForwardIterator>::value_type>)
1711 __glibcxx_requires_valid_range(__first, __middle);
1712 __glibcxx_requires_valid_range(__middle, __last);
1714 return std::copy(__first, __middle,
1715 std::copy(__middle, __last, __result));
1719 template<
typename _ForwardIterator,
typename _Predicate>
1724 if (__first == __last)
1727 while (__pred(*__first))
1728 if (++__first == __last)
1731 _ForwardIterator __next = __first;
1733 while (++__next != __last)
1734 if (__pred(*__next))
1744 template<
typename _B
idirectionalIterator,
typename _Predicate>
1745 _BidirectionalIterator
1746 __partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
1752 if (__first == __last)
1754 else if (__pred(*__first))
1760 if (__first == __last)
1762 else if (!
bool(__pred(*__last)))
1774 template<
typename _ForwardIterator,
typename _Predicate,
typename _Distance>
1777 _ForwardIterator __last,
1778 _Predicate __pred, _Distance __len)
1781 return __pred(*__first) ? __last : __first;
1782 _ForwardIterator __middle = __first;
1798 template<
typename _ForwardIterator,
typename _Pointer,
typename _Predicate,
1802 _ForwardIterator __last,
1803 _Predicate __pred, _Distance __len,
1805 _Distance __buffer_size)
1807 if (__len <= __buffer_size)
1809 _ForwardIterator __result1 = __first;
1810 _Pointer __result2 = __buffer;
1811 for (; __first != __last; ++__first)
1812 if (__pred(*__first))
1814 if (__result1 != __first)
1815 *__result1 = _GLIBCXX_MOVE(*__first);
1820 *__result2 = _GLIBCXX_MOVE(*__first);
1823 _GLIBCXX_MOVE3(__buffer, __result2, __result1);
1828 _ForwardIterator __middle = __first;
1830 _ForwardIterator __begin =
1832 __len / 2, __buffer,
1834 _ForwardIterator __end =
1837 __buffer, __buffer_size);
1861 template<
typename _ForwardIterator,
typename _Predicate>
1863 stable_partition(_ForwardIterator __first, _ForwardIterator __last,
1867 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
1869 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
1870 typename iterator_traits<_ForwardIterator>::value_type>)
1871 __glibcxx_requires_valid_range(__first, __last);
1873 if (__first == __last)
1877 typedef typename iterator_traits<_ForwardIterator>::value_type
1879 typedef typename iterator_traits<_ForwardIterator>::difference_type
1884 if (__buf.
size() > 0)
1889 _DistanceType(__buf.
size()));
1898 template<
typename _RandomAccessIterator>
1901 _RandomAccessIterator __middle,
1902 _RandomAccessIterator __last)
1905 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1906 if (*__i < *__first)
1907 std::__pop_heap(__first, __middle, __i);
1911 template<
typename _RandomAccessIterator,
typename _Compare>
1914 _RandomAccessIterator __middle,
1915 _RandomAccessIterator __last, _Compare __comp)
1918 for (_RandomAccessIterator __i = __middle; __i < __last; ++__i)
1919 if (__comp(*__i, *__first))
1920 std::__pop_heap(__first, __middle, __i, __comp);
1943 template<
typename _InputIterator,
typename _RandomAccessIterator>
1944 _RandomAccessIterator
1945 partial_sort_copy(_InputIterator __first, _InputIterator __last,
1946 _RandomAccessIterator __result_first,
1947 _RandomAccessIterator __result_last)
1949 typedef typename iterator_traits<_InputIterator>::value_type
1951 typedef typename iterator_traits<_RandomAccessIterator>::value_type
1953 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
1957 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
1958 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
1960 __glibcxx_function_requires(_LessThanOpConcept<_InputValueType,
1962 __glibcxx_function_requires(_LessThanComparableConcept<_OutputValueType>)
1963 __glibcxx_requires_valid_range(__first, __last);
1964 __glibcxx_requires_valid_range(__result_first, __result_last);
1966 if (__result_first == __result_last)
1967 return __result_last;
1968 _RandomAccessIterator __result_real_last = __result_first;
1969 while(__first != __last && __result_real_last != __result_last)
1971 *__result_real_last = *__first;
1972 ++__result_real_last;
1976 while (__first != __last)
1978 if (*__first < *__result_first)
1979 std::__adjust_heap(__result_first, _DistanceType(0),
1980 _DistanceType(__result_real_last
1982 _InputValueType(*__first));
1986 return __result_real_last;
2009 template<
typename _InputIterator,
typename _RandomAccessIterator,
typename _Compare>
2010 _RandomAccessIterator
2011 partial_sort_copy(_InputIterator __first, _InputIterator __last,
2012 _RandomAccessIterator __result_first,
2013 _RandomAccessIterator __result_last,
2016 typedef typename iterator_traits<_InputIterator>::value_type
2018 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2020 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
2024 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
2025 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
2026 _RandomAccessIterator>)
2027 __glibcxx_function_requires(_ConvertibleConcept<_InputValueType,
2029 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2030 _InputValueType, _OutputValueType>)
2031 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2032 _OutputValueType, _OutputValueType>)
2033 __glibcxx_requires_valid_range(__first, __last);
2034 __glibcxx_requires_valid_range(__result_first, __result_last);
2036 if (__result_first == __result_last)
2037 return __result_last;
2038 _RandomAccessIterator __result_real_last = __result_first;
2039 while(__first != __last && __result_real_last != __result_last)
2041 *__result_real_last = *__first;
2042 ++__result_real_last;
2046 while (__first != __last)
2048 if (__comp(*__first, *__result_first))
2049 std::__adjust_heap(__result_first, _DistanceType(0),
2050 _DistanceType(__result_real_last
2052 _InputValueType(*__first),
2057 return __result_real_last;
2061 template<
typename _RandomAccessIterator>
2065 typename iterator_traits<_RandomAccessIterator>::value_type
2066 __val = _GLIBCXX_MOVE(*__last);
2067 _RandomAccessIterator __next = __last;
2069 while (__val < *__next)
2071 *__last = _GLIBCXX_MOVE(*__next);
2075 *__last = _GLIBCXX_MOVE(__val);
2079 template<
typename _RandomAccessIterator,
typename _Compare>
2084 typename iterator_traits<_RandomAccessIterator>::value_type
2085 __val = _GLIBCXX_MOVE(*__last);
2086 _RandomAccessIterator __next = __last;
2088 while (__comp(__val, *__next))
2090 *__last = _GLIBCXX_MOVE(*__next);
2094 *__last = _GLIBCXX_MOVE(__val);
2098 template<
typename _RandomAccessIterator>
2101 _RandomAccessIterator __last)
2103 if (__first == __last)
2106 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2108 if (*__i < *__first)
2110 typename iterator_traits<_RandomAccessIterator>::value_type
2111 __val = _GLIBCXX_MOVE(*__i);
2112 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2113 *__first = _GLIBCXX_MOVE(__val);
2121 template<
typename _RandomAccessIterator,
typename _Compare>
2124 _RandomAccessIterator __last, _Compare __comp)
2126 if (__first == __last)
return;
2128 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
2130 if (__comp(*__i, *__first))
2132 typename iterator_traits<_RandomAccessIterator>::value_type
2133 __val = _GLIBCXX_MOVE(*__i);
2134 _GLIBCXX_MOVE_BACKWARD3(__first, __i, __i + 1);
2135 *__first = _GLIBCXX_MOVE(__val);
2143 template<
typename _RandomAccessIterator>
2146 _RandomAccessIterator __last)
2148 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2151 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2156 template<
typename _RandomAccessIterator,
typename _Compare>
2159 _RandomAccessIterator __last, _Compare __comp)
2161 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2164 for (_RandomAccessIterator __i = __first; __i != __last; ++__i)
2172 enum { _S_threshold = 16 };
2175 template<
typename _RandomAccessIterator>
2178 _RandomAccessIterator __last)
2180 if (__last - __first >
int(_S_threshold))
2190 template<
typename _RandomAccessIterator,
typename _Compare>
2193 _RandomAccessIterator __last, _Compare __comp)
2195 if (__last - __first >
int(_S_threshold))
2206 template<
typename _RandomAccessIterator,
typename _Tp>
2207 _RandomAccessIterator
2209 _RandomAccessIterator __last,
const _Tp& __pivot)
2213 while (*__first < __pivot)
2216 while (__pivot < *__last)
2218 if (!(__first < __last))
2226 template<
typename _RandomAccessIterator,
typename _Tp,
typename _Compare>
2227 _RandomAccessIterator
2229 _RandomAccessIterator __last,
2230 const _Tp& __pivot, _Compare __comp)
2234 while (__comp(*__first, __pivot))
2237 while (__comp(__pivot, *__last))
2239 if (!(__first < __last))
2247 template<
typename _RandomAccessIterator>
2248 inline _RandomAccessIterator
2250 _RandomAccessIterator __last)
2252 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2259 template<
typename _RandomAccessIterator,
typename _Compare>
2260 inline _RandomAccessIterator
2262 _RandomAccessIterator __last, _Compare __comp)
2264 _RandomAccessIterator __mid = __first + (__last - __first) / 2;
2270 template<
typename _RandomAccessIterator,
typename _Size>
2273 _RandomAccessIterator __last,
2274 _Size __depth_limit)
2276 while (__last - __first >
int(_S_threshold))
2278 if (__depth_limit == 0)
2280 _GLIBCXX_STD_A::partial_sort(__first, __last, __last);
2284 _RandomAccessIterator __cut =
2292 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2295 _RandomAccessIterator __last,
2296 _Size __depth_limit, _Compare __comp)
2298 while (__last - __first >
int(_S_threshold))
2300 if (__depth_limit == 0)
2302 _GLIBCXX_STD_A::partial_sort(__first, __last, __last, __comp);
2306 _RandomAccessIterator __cut =
2315 template<
typename _RandomAccessIterator,
typename _Size>
2317 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2318 _RandomAccessIterator __last, _Size __depth_limit)
2320 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2323 while (__last - __first > 3)
2325 if (__depth_limit == 0)
2330 std::iter_swap(__first, __nth);
2334 _RandomAccessIterator __cut =
2344 template<
typename _RandomAccessIterator,
typename _Size,
typename _Compare>
2346 __introselect(_RandomAccessIterator __first, _RandomAccessIterator __nth,
2347 _RandomAccessIterator __last, _Size __depth_limit,
2350 typedef typename iterator_traits<_RandomAccessIterator>::value_type
2353 while (__last - __first > 3)
2355 if (__depth_limit == 0)
2363 _RandomAccessIterator __cut =
2393 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2395 lower_bound(_ForwardIterator __first, _ForwardIterator __last,
2396 const _Tp& __val, _Compare __comp)
2398 typedef typename iterator_traits<_ForwardIterator>::value_type
2400 typedef typename iterator_traits<_ForwardIterator>::difference_type
2404 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2405 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2407 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2414 _DistanceType __half = __len >> 1;
2415 _ForwardIterator __middle = __first;
2417 if (__comp(*__middle, __val))
2421 __len = __len - __half - 1;
2440 template<
typename _ForwardIterator,
typename _Tp>
2442 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2445 typedef typename iterator_traits<_ForwardIterator>::value_type
2447 typedef typename iterator_traits<_ForwardIterator>::difference_type
2451 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2452 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2453 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2459 _DistanceType __half = __len >> 1;
2460 _ForwardIterator __middle = __first;
2462 if (__val < *__middle)
2468 __len = __len - __half - 1;
2489 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2491 upper_bound(_ForwardIterator __first, _ForwardIterator __last,
2492 const _Tp& __val, _Compare __comp)
2494 typedef typename iterator_traits<_ForwardIterator>::value_type
2496 typedef typename iterator_traits<_ForwardIterator>::difference_type
2500 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2501 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2503 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2510 _DistanceType __half = __len >> 1;
2511 _ForwardIterator __middle = __first;
2513 if (__comp(__val, *__middle))
2519 __len = __len - __half - 1;
2542 template<
typename _ForwardIterator,
typename _Tp>
2543 pair<_ForwardIterator, _ForwardIterator>
2544 equal_range(_ForwardIterator __first, _ForwardIterator __last,
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(_LessThanOpConcept<_ValueType, _Tp>)
2555 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2556 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2557 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2563 _DistanceType __half = __len >> 1;
2564 _ForwardIterator __middle = __first;
2566 if (*__middle < __val)
2570 __len = __len - __half - 1;
2572 else if (__val < *__middle)
2604 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2605 pair<_ForwardIterator, _ForwardIterator>
2606 equal_range(_ForwardIterator __first, _ForwardIterator __last,
2607 const _Tp& __val, _Compare __comp)
2609 typedef typename iterator_traits<_ForwardIterator>::value_type
2611 typedef typename iterator_traits<_ForwardIterator>::difference_type
2615 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2616 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2618 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2620 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2622 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2629 _DistanceType __half = __len >> 1;
2630 _ForwardIterator __middle = __first;
2632 if (__comp(*__middle, __val))
2636 __len = __len - __half - 1;
2638 else if (__comp(__val, *__middle))
2664 template<
typename _ForwardIterator,
typename _Tp>
2666 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2669 typedef typename iterator_traits<_ForwardIterator>::value_type
2673 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2674 __glibcxx_function_requires(_LessThanOpConcept<_Tp, _ValueType>)
2675 __glibcxx_requires_partitioned_lower(__first, __last, __val);
2676 __glibcxx_requires_partitioned_upper(__first, __last, __val);
2679 return __i != __last && !(__val < *__i);
2697 template<
typename _ForwardIterator,
typename _Tp,
typename _Compare>
2699 binary_search(_ForwardIterator __first, _ForwardIterator __last,
2700 const _Tp& __val, _Compare __comp)
2702 typedef typename iterator_traits<_ForwardIterator>::value_type
2706 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
2707 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
2709 __glibcxx_requires_partitioned_lower_pred(__first, __last,
2711 __glibcxx_requires_partitioned_upper_pred(__first, __last,
2715 return __i != __last && !bool(__comp(__val, *__i));
2721 template<
typename _InputIterator1,
typename _InputIterator2,
2722 typename _OutputIterator>
2725 _InputIterator2 __first2, _InputIterator2 __last2,
2726 _OutputIterator __result)
2728 while (__first1 != __last1 && __first2 != __last2)
2730 if (*__first2 < *__first1)
2732 *__result = _GLIBCXX_MOVE(*__first2);
2737 *__result = _GLIBCXX_MOVE(*__first1);
2742 if (__first1 != __last1)
2743 _GLIBCXX_MOVE3(__first1, __last1, __result);
2747 template<
typename _InputIterator1,
typename _InputIterator2,
2748 typename _OutputIterator,
typename _Compare>
2751 _InputIterator2 __first2, _InputIterator2 __last2,
2752 _OutputIterator __result, _Compare __comp)
2754 while (__first1 != __last1 && __first2 != __last2)
2756 if (__comp(*__first2, *__first1))
2758 *__result = _GLIBCXX_MOVE(*__first2);
2763 *__result = _GLIBCXX_MOVE(*__first1);
2768 if (__first1 != __last1)
2769 _GLIBCXX_MOVE3(__first1, __last1, __result);
2773 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2774 typename _BidirectionalIterator3>
2777 _BidirectionalIterator1 __last1,
2778 _BidirectionalIterator2 __first2,
2779 _BidirectionalIterator2 __last2,
2780 _BidirectionalIterator3 __result)
2782 if (__first1 == __last1)
2784 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2787 else if (__first2 == __last2)
2794 if (*__last2 < *__last1)
2796 *--__result = _GLIBCXX_MOVE(*__last1);
2797 if (__first1 == __last1)
2799 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2806 *--__result = _GLIBCXX_MOVE(*__last2);
2807 if (__first2 == __last2)
2815 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2816 typename _BidirectionalIterator3,
typename _Compare>
2819 _BidirectionalIterator1 __last1,
2820 _BidirectionalIterator2 __first2,
2821 _BidirectionalIterator2 __last2,
2822 _BidirectionalIterator3 __result,
2825 if (__first1 == __last1)
2827 _GLIBCXX_MOVE_BACKWARD3(__first2, __last2, __result);
2830 else if (__first2 == __last2)
2837 if (__comp(*__last2, *__last1))
2839 *--__result = _GLIBCXX_MOVE(*__last1);
2840 if (__first1 == __last1)
2842 _GLIBCXX_MOVE_BACKWARD3(__first2, ++__last2, __result);
2849 *--__result = _GLIBCXX_MOVE(*__last2);
2850 if (__first2 == __last2)
2858 template<
typename _BidirectionalIterator1,
typename _BidirectionalIterator2,
2860 _BidirectionalIterator1
2862 _BidirectionalIterator1 __middle,
2863 _BidirectionalIterator1 __last,
2864 _Distance __len1, _Distance __len2,
2865 _BidirectionalIterator2 __buffer,
2866 _Distance __buffer_size)
2868 _BidirectionalIterator2 __buffer_end;
2869 if (__len1 > __len2 && __len2 <= __buffer_size)
2873 __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2874 _GLIBCXX_MOVE_BACKWARD3(__first, __middle, __last);
2875 return _GLIBCXX_MOVE3(__buffer, __buffer_end, __first);
2880 else if (__len1 <= __buffer_size)
2884 __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2885 _GLIBCXX_MOVE3(__middle, __last, __first);
2886 return _GLIBCXX_MOVE_BACKWARD3(__buffer, __buffer_end, __last);
2900 template<
typename _BidirectionalIterator,
typename _Distance,
2904 _BidirectionalIterator __middle,
2905 _BidirectionalIterator __last,
2906 _Distance __len1, _Distance __len2,
2907 _Pointer __buffer, _Distance __buffer_size)
2909 if (__len1 <= __len2 && __len1 <= __buffer_size)
2911 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2915 else if (__len2 <= __buffer_size)
2917 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2919 __buffer_end, __last);
2923 _BidirectionalIterator __first_cut = __first;
2924 _BidirectionalIterator __second_cut = __middle;
2925 _Distance __len11 = 0;
2926 _Distance __len22 = 0;
2927 if (__len1 > __len2)
2929 __len11 = __len1 / 2;
2937 __len22 = __len2 / 2;
2943 _BidirectionalIterator __new_middle =
2945 __len1 - __len11, __len22, __buffer,
2948 __len22, __buffer, __buffer_size);
2951 __len2 - __len22, __buffer, __buffer_size);
2956 template<
typename _BidirectionalIterator,
typename _Distance,
2957 typename _Pointer,
typename _Compare>
2960 _BidirectionalIterator __middle,
2961 _BidirectionalIterator __last,
2962 _Distance __len1, _Distance __len2,
2963 _Pointer __buffer, _Distance __buffer_size,
2966 if (__len1 <= __len2 && __len1 <= __buffer_size)
2968 _Pointer __buffer_end = _GLIBCXX_MOVE3(__first, __middle, __buffer);
2972 else if (__len2 <= __buffer_size)
2974 _Pointer __buffer_end = _GLIBCXX_MOVE3(__middle, __last, __buffer);
2976 __buffer_end, __last, __comp);
2980 _BidirectionalIterator __first_cut = __first;
2981 _BidirectionalIterator __second_cut = __middle;
2982 _Distance __len11 = 0;
2983 _Distance __len22 = 0;
2984 if (__len1 > __len2)
2986 __len11 = __len1 / 2;
2994 __len22 = __len2 / 2;
3000 _BidirectionalIterator __new_middle =
3002 __len1 - __len11, __len22, __buffer,
3005 __len22, __buffer, __buffer_size, __comp);
3008 __len2 - __len22, __buffer,
3009 __buffer_size, __comp);
3014 template<
typename _B
idirectionalIterator,
typename _Distance>
3017 _BidirectionalIterator __middle,
3018 _BidirectionalIterator __last,
3019 _Distance __len1, _Distance __len2)
3021 if (__len1 == 0 || __len2 == 0)
3023 if (__len1 + __len2 == 2)
3025 if (*__middle < *__first)
3029 _BidirectionalIterator __first_cut = __first;
3030 _BidirectionalIterator __second_cut = __middle;
3031 _Distance __len11 = 0;
3032 _Distance __len22 = 0;
3033 if (__len1 > __len2)
3035 __len11 = __len1 / 2;
3042 __len22 = __len2 / 2;
3048 _BidirectionalIterator __new_middle = __first_cut;
3053 __len1 - __len11, __len2 - __len22);
3057 template<
typename _BidirectionalIterator,
typename _Distance,
3061 _BidirectionalIterator __middle,
3062 _BidirectionalIterator __last,
3063 _Distance __len1, _Distance __len2,
3066 if (__len1 == 0 || __len2 == 0)
3068 if (__len1 + __len2 == 2)
3070 if (__comp(*__middle, *__first))
3074 _BidirectionalIterator __first_cut = __first;
3075 _BidirectionalIterator __second_cut = __middle;
3076 _Distance __len11 = 0;
3077 _Distance __len22 = 0;
3078 if (__len1 > __len2)
3080 __len11 = __len1 / 2;
3088 __len22 = __len2 / 2;
3095 _BidirectionalIterator __new_middle = __first_cut;
3098 __len11, __len22, __comp);
3100 __len1 - __len11, __len2 - __len22, __comp);
3121 template<
typename _B
idirectionalIterator>
3123 inplace_merge(_BidirectionalIterator __first,
3124 _BidirectionalIterator __middle,
3125 _BidirectionalIterator __last)
3127 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3129 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3133 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3134 _BidirectionalIterator>)
3135 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
3136 __glibcxx_requires_sorted(__first, __middle);
3137 __glibcxx_requires_sorted(__middle, __last);
3139 if (__first == __middle || __middle == __last)
3147 if (__buf.
begin() == 0)
3151 __buf.
begin(), _DistanceType(__buf.
size()));
3176 template<
typename _B
idirectionalIterator,
typename _Compare>
3178 inplace_merge(_BidirectionalIterator __first,
3179 _BidirectionalIterator __middle,
3180 _BidirectionalIterator __last,
3183 typedef typename iterator_traits<_BidirectionalIterator>::value_type
3185 typedef typename iterator_traits<_BidirectionalIterator>::difference_type
3189 __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<
3190 _BidirectionalIterator>)
3191 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3192 _ValueType, _ValueType>)
3193 __glibcxx_requires_sorted_pred(__first, __middle, __comp);
3194 __glibcxx_requires_sorted_pred(__middle, __last, __comp);
3196 if (__first == __middle || __middle == __last)
3199 const _DistanceType __len1 =
std::distance(__first, __middle);
3200 const _DistanceType __len2 =
std::distance(__middle, __last);
3204 if (__buf.
begin() == 0)
3209 __buf.
begin(), _DistanceType(__buf.
size()),
3215 template<
typename _InputIterator1,
typename _InputIterator2,
3216 typename _OutputIterator>
3219 _InputIterator2 __first2, _InputIterator2 __last2,
3220 _OutputIterator __result)
3222 while (__first1 != __last1 && __first2 != __last2)
3224 if (*__first2 < *__first1)
3226 *__result = _GLIBCXX_MOVE(*__first2);
3231 *__result = _GLIBCXX_MOVE(*__first1);
3236 return _GLIBCXX_MOVE3(__first2, __last2,
3237 _GLIBCXX_MOVE3(__first1, __last1,
3242 template<
typename _InputIterator1,
typename _InputIterator2,
3243 typename _OutputIterator,
typename _Compare>
3246 _InputIterator2 __first2, _InputIterator2 __last2,
3247 _OutputIterator __result, _Compare __comp)
3249 while (__first1 != __last1 && __first2 != __last2)
3251 if (__comp(*__first2, *__first1))
3253 *__result = _GLIBCXX_MOVE(*__first2);
3258 *__result = _GLIBCXX_MOVE(*__first1);
3263 return _GLIBCXX_MOVE3(__first2, __last2,
3264 _GLIBCXX_MOVE3(__first1, __last1,
3268 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
3271 __merge_sort_loop(_RandomAccessIterator1 __first,
3272 _RandomAccessIterator1 __last,
3273 _RandomAccessIterator2 __result,
3274 _Distance __step_size)
3276 const _Distance __two_step = 2 * __step_size;
3278 while (__last - __first >= __two_step)
3281 __first + __step_size,
3282 __first + __two_step, __result);
3283 __first += __two_step;
3286 __step_size =
std::min(_Distance(__last - __first), __step_size);
3288 __first + __step_size, __last, __result);
3291 template<
typename _RandomAccessIterator1,
typename _RandomAccessIterator2,
3292 typename _Distance,
typename _Compare>
3294 __merge_sort_loop(_RandomAccessIterator1 __first,
3295 _RandomAccessIterator1 __last,
3296 _RandomAccessIterator2 __result, _Distance __step_size,
3299 const _Distance __two_step = 2 * __step_size;
3301 while (__last - __first >= __two_step)
3304 __first + __step_size,
3305 __first + __two_step,
3307 __first += __two_step;
3309 __step_size =
std::min(_Distance(__last - __first), __step_size);
3312 __first + __step_size, __last, __result, __comp);
3315 template<
typename _RandomAccessIterator,
typename _Distance>
3317 __chunk_insertion_sort(_RandomAccessIterator __first,
3318 _RandomAccessIterator __last,
3319 _Distance __chunk_size)
3321 while (__last - __first >= __chunk_size)
3324 __first += __chunk_size;
3329 template<
typename _RandomAccessIterator,
typename _Distance,
3332 __chunk_insertion_sort(_RandomAccessIterator __first,
3333 _RandomAccessIterator __last,
3334 _Distance __chunk_size, _Compare __comp)
3336 while (__last - __first >= __chunk_size)
3339 __first += __chunk_size;
3344 enum { _S_chunk_size = 7 };
3346 template<
typename _RandomAccessIterator,
typename _Po
inter>
3348 __merge_sort_with_buffer(_RandomAccessIterator __first,
3349 _RandomAccessIterator __last,
3352 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3355 const _Distance __len = __last - __first;
3356 const _Pointer __buffer_last = __buffer + __len;
3358 _Distance __step_size = _S_chunk_size;
3359 std::__chunk_insertion_sort(__first, __last, __step_size);
3361 while (__step_size < __len)
3363 std::__merge_sort_loop(__first, __last, __buffer, __step_size);
3365 std::__merge_sort_loop(__buffer, __buffer_last, __first, __step_size);
3370 template<
typename _RandomAccessIterator,
typename _Po
inter,
typename _Compare>
3372 __merge_sort_with_buffer(_RandomAccessIterator __first,
3373 _RandomAccessIterator __last,
3374 _Pointer __buffer, _Compare __comp)
3376 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
3379 const _Distance __len = __last - __first;
3380 const _Pointer __buffer_last = __buffer + __len;
3382 _Distance __step_size = _S_chunk_size;
3383 std::__chunk_insertion_sort(__first, __last, __step_size, __comp);
3385 while (__step_size < __len)
3387 std::__merge_sort_loop(__first, __last, __buffer,
3388 __step_size, __comp);
3390 std::__merge_sort_loop(__buffer, __buffer_last, __first,
3391 __step_size, __comp);
3396 template<
typename _RandomAccessIterator,
typename _Pointer,
3399 __stable_sort_adaptive(_RandomAccessIterator __first,
3400 _RandomAccessIterator __last,
3401 _Pointer __buffer, _Distance __buffer_size)
3403 const _Distance __len = (__last - __first + 1) / 2;
3404 const _RandomAccessIterator __middle = __first + __len;
3405 if (__len > __buffer_size)
3407 std::__stable_sort_adaptive(__first, __middle,
3408 __buffer, __buffer_size);
3409 std::__stable_sort_adaptive(__middle, __last,
3410 __buffer, __buffer_size);
3414 std::__merge_sort_with_buffer(__first, __middle, __buffer);
3415 std::__merge_sort_with_buffer(__middle, __last, __buffer);
3418 _Distance(__middle - __first),
3419 _Distance(__last - __middle),
3420 __buffer, __buffer_size);
3423 template<
typename _RandomAccessIterator,
typename _Pointer,
3424 typename _Distance,
typename _Compare>
3426 __stable_sort_adaptive(_RandomAccessIterator __first,
3427 _RandomAccessIterator __last,
3428 _Pointer __buffer, _Distance __buffer_size,
3431 const _Distance __len = (__last - __first + 1) / 2;
3432 const _RandomAccessIterator __middle = __first + __len;
3433 if (__len > __buffer_size)
3435 std::__stable_sort_adaptive(__first, __middle, __buffer,
3436 __buffer_size, __comp);
3437 std::__stable_sort_adaptive(__middle, __last, __buffer,
3438 __buffer_size, __comp);
3442 std::__merge_sort_with_buffer(__first, __middle, __buffer, __comp);
3443 std::__merge_sort_with_buffer(__middle, __last, __buffer, __comp);
3446 _Distance(__middle - __first),
3447 _Distance(__last - __middle),
3448 __buffer, __buffer_size,
3453 template<
typename _RandomAccessIterator>
3456 _RandomAccessIterator __last)
3458 if (__last - __first < 15)
3463 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3472 template<
typename _RandomAccessIterator,
typename _Compare>
3475 _RandomAccessIterator __last, _Compare __comp)
3477 if (__last - __first < 15)
3482 _RandomAccessIterator __middle = __first + (__last - __first) / 2;
3514 template<
typename _InputIterator1,
typename _InputIterator2>
3516 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3517 _InputIterator2 __first2, _InputIterator2 __last2)
3519 typedef typename iterator_traits<_InputIterator1>::value_type
3521 typedef typename iterator_traits<_InputIterator2>::value_type
3525 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3526 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3527 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
3528 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
3529 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
3530 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
3532 while (__first1 != __last1 && __first2 != __last2)
3533 if (*__first2 < *__first1)
3535 else if(*__first1 < *__first2)
3538 ++__first1, ++__first2;
3540 return __first2 == __last2;
3563 template<
typename _InputIterator1,
typename _InputIterator2,
3566 includes(_InputIterator1 __first1, _InputIterator1 __last1,
3567 _InputIterator2 __first2, _InputIterator2 __last2,
3570 typedef typename iterator_traits<_InputIterator1>::value_type
3572 typedef typename iterator_traits<_InputIterator2>::value_type
3576 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
3577 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
3578 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3579 _ValueType1, _ValueType2>)
3580 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3581 _ValueType2, _ValueType1>)
3582 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
3583 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
3585 while (__first1 != __last1 && __first2 != __last2)
3586 if (__comp(*__first2, *__first1))
3588 else if(__comp(*__first1, *__first2))
3591 ++__first1, ++__first2;
3593 return __first2 == __last2;
3618 template<
typename _B
idirectionalIterator>
3620 next_permutation(_BidirectionalIterator __first,
3621 _BidirectionalIterator __last)
3624 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3625 _BidirectionalIterator>)
3626 __glibcxx_function_requires(_LessThanComparableConcept<
3627 typename iterator_traits<_BidirectionalIterator>::value_type>)
3628 __glibcxx_requires_valid_range(__first, __last);
3630 if (__first == __last)
3632 _BidirectionalIterator __i = __first;
3641 _BidirectionalIterator __ii = __i;
3645 _BidirectionalIterator __j = __last;
3646 while (!(*__i < *--__j))
3675 template<
typename _B
idirectionalIterator,
typename _Compare>
3677 next_permutation(_BidirectionalIterator __first,
3678 _BidirectionalIterator __last, _Compare __comp)
3681 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3682 _BidirectionalIterator>)
3683 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3684 typename iterator_traits<_BidirectionalIterator>::value_type,
3685 typename iterator_traits<_BidirectionalIterator>::value_type>)
3686 __glibcxx_requires_valid_range(__first, __last);
3688 if (__first == __last)
3690 _BidirectionalIterator __i = __first;
3699 _BidirectionalIterator __ii = __i;
3701 if (__comp(*__i, *__ii))
3703 _BidirectionalIterator __j = __last;
3704 while (!
bool(__comp(*__i, *--__j)))
3731 template<
typename _B
idirectionalIterator>
3733 prev_permutation(_BidirectionalIterator __first,
3734 _BidirectionalIterator __last)
3737 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3738 _BidirectionalIterator>)
3739 __glibcxx_function_requires(_LessThanComparableConcept<
3740 typename iterator_traits<_BidirectionalIterator>::value_type>)
3741 __glibcxx_requires_valid_range(__first, __last);
3743 if (__first == __last)
3745 _BidirectionalIterator __i = __first;
3754 _BidirectionalIterator __ii = __i;
3758 _BidirectionalIterator __j = __last;
3759 while (!(*--__j < *__i))
3788 template<
typename _B
idirectionalIterator,
typename _Compare>
3790 prev_permutation(_BidirectionalIterator __first,
3791 _BidirectionalIterator __last, _Compare __comp)
3794 __glibcxx_function_requires(_BidirectionalIteratorConcept<
3795 _BidirectionalIterator>)
3796 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3797 typename iterator_traits<_BidirectionalIterator>::value_type,
3798 typename iterator_traits<_BidirectionalIterator>::value_type>)
3799 __glibcxx_requires_valid_range(__first, __last);
3801 if (__first == __last)
3803 _BidirectionalIterator __i = __first;
3812 _BidirectionalIterator __ii = __i;
3814 if (__comp(*__ii, *__i))
3816 _BidirectionalIterator __j = __last;
3817 while (!
bool(__comp(*--__j, *__i)))
3848 template<
typename _InputIterator,
typename _OutputIterator,
typename _Tp>
3850 replace_copy(_InputIterator __first, _InputIterator __last,
3851 _OutputIterator __result,
3852 const _Tp& __old_value,
const _Tp& __new_value)
3855 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3856 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3857 typename iterator_traits<_InputIterator>::value_type>)
3858 __glibcxx_function_requires(_EqualOpConcept<
3859 typename iterator_traits<_InputIterator>::value_type, _Tp>)
3860 __glibcxx_requires_valid_range(__first, __last);
3862 for (; __first != __last; ++__first, ++__result)
3863 if (*__first == __old_value)
3864 *__result = __new_value;
3866 *__result = *__first;
3885 template<
typename _InputIterator,
typename _OutputIterator,
3886 typename _Predicate,
typename _Tp>
3888 replace_copy_if(_InputIterator __first, _InputIterator __last,
3889 _OutputIterator __result,
3890 _Predicate __pred,
const _Tp& __new_value)
3893 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
3894 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
3895 typename iterator_traits<_InputIterator>::value_type>)
3896 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
3897 typename iterator_traits<_InputIterator>::value_type>)
3898 __glibcxx_requires_valid_range(__first, __last);
3900 for (; __first != __last; ++__first, ++__result)
3901 if (__pred(*__first))
3902 *__result = __new_value;
3904 *__result = *__first;
3908 #ifdef __GXX_EXPERIMENTAL_CXX0X__
3916 template<
typename _ForwardIterator>
3918 is_sorted(_ForwardIterator __first, _ForwardIterator __last)
3930 template<
typename _ForwardIterator,
typename _Compare>
3932 is_sorted(_ForwardIterator __first, _ForwardIterator __last,
3944 template<
typename _ForwardIterator>
3946 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last)
3949 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3950 __glibcxx_function_requires(_LessThanComparableConcept<
3951 typename iterator_traits<_ForwardIterator>::value_type>)
3952 __glibcxx_requires_valid_range(__first, __last);
3954 if (__first == __last)
3957 _ForwardIterator __next = __first;
3958 for (++__next; __next != __last; __first = __next, ++__next)
3959 if (*__next < *__first)
3973 template<
typename _ForwardIterator,
typename _Compare>
3975 is_sorted_until(_ForwardIterator __first, _ForwardIterator __last,
3979 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
3980 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
3981 typename iterator_traits<_ForwardIterator>::value_type,
3982 typename iterator_traits<_ForwardIterator>::value_type>)
3983 __glibcxx_requires_valid_range(__first, __last);
3985 if (__first == __last)
3988 _ForwardIterator __next = __first;
3989 for (++__next; __next != __last; __first = __next, ++__next)
3990 if (__comp(*__next, *__first))
4002 template<
typename _Tp>
4003 inline pair<const _Tp&, const _Tp&>
4007 __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
4009 return __b < __a ? pair<const _Tp&, const _Tp&>(__b, __a)
4021 template<
typename _Tp,
typename _Compare>
4022 inline pair<const _Tp&, const _Tp&>
4023 minmax(
const _Tp& __a,
const _Tp& __b, _Compare __comp)
4040 template<
typename _ForwardIterator>
4041 pair<_ForwardIterator, _ForwardIterator>
4042 minmax_element(_ForwardIterator __first, _ForwardIterator __last)
4045 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4046 __glibcxx_function_requires(_LessThanComparableConcept<
4047 typename iterator_traits<_ForwardIterator>::value_type>)
4048 __glibcxx_requires_valid_range(__first, __last);
4050 _ForwardIterator __next = __first;
4051 if (__first == __last
4052 || ++__next == __last)
4055 _ForwardIterator __min, __max;
4056 if (*__next < *__first)
4070 while (__first != __last)
4073 if (++__next == __last)
4075 if (*__first < *__min)
4077 else if (!(*__first < *__max))
4082 if (*__next < *__first)
4084 if (*__next < *__min)
4086 if (!(*__first < *__max))
4091 if (*__first < *__min)
4093 if (!(*__next < *__max))
4116 template<
typename _ForwardIterator,
typename _Compare>
4117 pair<_ForwardIterator, _ForwardIterator>
4118 minmax_element(_ForwardIterator __first, _ForwardIterator __last,
4122 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4123 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
4124 typename iterator_traits<_ForwardIterator>::value_type,
4125 typename iterator_traits<_ForwardIterator>::value_type>)
4126 __glibcxx_requires_valid_range(__first, __last);
4128 _ForwardIterator __next = __first;
4129 if (__first == __last
4130 || ++__next == __last)
4133 _ForwardIterator __min, __max;
4134 if (__comp(*__next, *__first))
4148 while (__first != __last)
4151 if (++__next == __last)
4153 if (__comp(*__first, *__min))
4155 else if (!__comp(*__first, *__max))
4160 if (__comp(*__next, *__first))
4162 if (__comp(*__next, *__min))
4164 if (!__comp(*__first, *__max))
4169 if (__comp(*__first, *__min))
4171 if (!__comp(*__next, *__max))
4183 template<
typename _Tp>
4185 min(initializer_list<_Tp> __l)
4186 {
return *std::min_element(__l.begin(), __l.end()); }
4188 template<
typename _Tp,
typename _Compare>
4190 min(initializer_list<_Tp> __l, _Compare __comp)
4193 template<
typename _Tp>
4195 max(initializer_list<_Tp> __l)
4198 template<
typename _Tp,
typename _Compare>
4200 max(initializer_list<_Tp> __l, _Compare __comp)
4203 template<
typename _Tp>
4204 inline pair<_Tp, _Tp>
4205 minmax(initializer_list<_Tp> __l)
4207 pair<const _Tp*, const _Tp*> __p =
4212 template<
typename _Tp,
typename _Compare>
4213 inline pair<_Tp, _Tp>
4214 minmax(initializer_list<_Tp> __l, _Compare __comp)
4216 pair<const _Tp*, const _Tp*> __p =
4233 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4235 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4236 _ForwardIterator2 __first2)
4240 for (; __first1 != __last1; ++__first1, ++__first2)
4241 if (!(*__first1 == *__first2))
4244 if (__first1 == __last1)
4249 _ForwardIterator2 __last2 = __first2;
4251 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4253 if (__scan != _GLIBCXX_STD_A::find(__first1, __scan, *__scan))
4256 auto __matches =
std::count(__first2, __last2, *__scan);
4258 ||
std::count(__scan, __last1, *__scan) != __matches)
4277 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4278 typename _BinaryPredicate>
4280 is_permutation(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4281 _ForwardIterator2 __first2, _BinaryPredicate __pred)
4285 for (; __first1 != __last1; ++__first1, ++__first2)
4286 if (!
bool(__pred(*__first1, *__first2)))
4289 if (__first1 == __last1)
4294 _ForwardIterator2 __last2 = __first2;
4296 for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
4298 using std::placeholders::_1;
4300 if (__scan != _GLIBCXX_STD_A::find_if(__first1, __scan,
4308 std::bind(__pred, _1, *__scan)) != __matches)
4314 #ifdef _GLIBCXX_USE_C99_STDINT_TR1
4327 template<
typename _RandomAccessIterator,
4328 typename _UniformRandomNumberGenerator>
4330 shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
4331 _UniformRandomNumberGenerator&& __g)
4334 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
4335 _RandomAccessIterator>)
4336 __glibcxx_requires_valid_range(__first, __last);
4338 if (__first == __last)
4341 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
4344 typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
4346 typedef typename __distr_type::param_type __p_type;
4349 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
4350 std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
4354 #endif // __GXX_EXPERIMENTAL_CXX0X__
4356 _GLIBCXX_END_NAMESPACE_VERSION
4358 _GLIBCXX_BEGIN_NAMESPACE_ALGO
4372 template<
typename _InputIterator,
typename _Function>
4374 for_each(_InputIterator __first, _InputIterator __last, _Function __f)
4377 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4378 __glibcxx_requires_valid_range(__first, __last);
4379 for (; __first != __last; ++__first)
4381 return _GLIBCXX_MOVE(__f);
4393 template<
typename _InputIterator,
typename _Tp>
4394 inline _InputIterator
4395 find(_InputIterator __first, _InputIterator __last,
4399 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4400 __glibcxx_function_requires(_EqualOpConcept<
4401 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4402 __glibcxx_requires_valid_range(__first, __last);
4417 template<
typename _InputIterator,
typename _Predicate>
4418 inline _InputIterator
4419 find_if(_InputIterator __first, _InputIterator __last,
4423 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4424 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4425 typename iterator_traits<_InputIterator>::value_type>)
4426 __glibcxx_requires_valid_range(__first, __last);
4446 template<
typename _InputIterator,
typename _ForwardIterator>
4448 find_first_of(_InputIterator __first1, _InputIterator __last1,
4449 _ForwardIterator __first2, _ForwardIterator __last2)
4452 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4453 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4454 __glibcxx_function_requires(_EqualOpConcept<
4455 typename iterator_traits<_InputIterator>::value_type,
4456 typename iterator_traits<_ForwardIterator>::value_type>)
4457 __glibcxx_requires_valid_range(__first1, __last1);
4458 __glibcxx_requires_valid_range(__first2, __last2);
4460 for (; __first1 != __last1; ++__first1)
4461 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4462 if (*__first1 == *__iter)
4485 template<
typename _InputIterator,
typename _ForwardIterator,
4486 typename _BinaryPredicate>
4488 find_first_of(_InputIterator __first1, _InputIterator __last1,
4489 _ForwardIterator __first2, _ForwardIterator __last2,
4490 _BinaryPredicate __comp)
4493 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4494 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4495 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4496 typename iterator_traits<_InputIterator>::value_type,
4497 typename iterator_traits<_ForwardIterator>::value_type>)
4498 __glibcxx_requires_valid_range(__first1, __last1);
4499 __glibcxx_requires_valid_range(__first2, __last2);
4501 for (; __first1 != __last1; ++__first1)
4502 for (_ForwardIterator __iter = __first2; __iter != __last2; ++__iter)
4503 if (__comp(*__first1, *__iter))
4517 template<
typename _ForwardIterator>
4519 adjacent_find(_ForwardIterator __first, _ForwardIterator __last)
4522 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4523 __glibcxx_function_requires(_EqualityComparableConcept<
4524 typename iterator_traits<_ForwardIterator>::value_type>)
4525 __glibcxx_requires_valid_range(__first, __last);
4526 if (__first == __last)
4528 _ForwardIterator __next = __first;
4529 while(++__next != __last)
4531 if (*__first == *__next)
4549 template<
typename _ForwardIterator,
typename _BinaryPredicate>
4551 adjacent_find(_ForwardIterator __first, _ForwardIterator __last,
4552 _BinaryPredicate __binary_pred)
4555 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4556 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4557 typename iterator_traits<_ForwardIterator>::value_type,
4558 typename iterator_traits<_ForwardIterator>::value_type>)
4559 __glibcxx_requires_valid_range(__first, __last);
4560 if (__first == __last)
4562 _ForwardIterator __next = __first;
4563 while(++__next != __last)
4565 if (__binary_pred(*__first, *__next))
4581 template<
typename _InputIterator,
typename _Tp>
4582 typename iterator_traits<_InputIterator>::difference_type
4583 count(_InputIterator __first, _InputIterator __last,
const _Tp& __value)
4586 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4587 __glibcxx_function_requires(_EqualOpConcept<
4588 typename iterator_traits<_InputIterator>::value_type, _Tp>)
4589 __glibcxx_requires_valid_range(__first, __last);
4590 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4591 for (; __first != __last; ++__first)
4592 if (*__first == __value)
4606 template<
typename _InputIterator,
typename _Predicate>
4607 typename iterator_traits<_InputIterator>::difference_type
4608 count_if(_InputIterator __first, _InputIterator __last, _Predicate __pred)
4611 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4612 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4613 typename iterator_traits<_InputIterator>::value_type>)
4614 __glibcxx_requires_valid_range(__first, __last);
4615 typename iterator_traits<_InputIterator>::difference_type __n = 0;
4616 for (; __first != __last; ++__first)
4617 if (__pred(*__first))
4646 template<
typename _ForwardIterator1,
typename _ForwardIterator2>
4648 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4649 _ForwardIterator2 __first2, _ForwardIterator2 __last2)
4652 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4653 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4654 __glibcxx_function_requires(_EqualOpConcept<
4655 typename iterator_traits<_ForwardIterator1>::value_type,
4656 typename iterator_traits<_ForwardIterator2>::value_type>)
4657 __glibcxx_requires_valid_range(__first1, __last1);
4658 __glibcxx_requires_valid_range(__first2, __last2);
4661 if (__first1 == __last1 || __first2 == __last2)
4665 _ForwardIterator2 __p1(__first2);
4666 if (++__p1 == __last2)
4667 return _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4670 _ForwardIterator2 __p;
4671 _ForwardIterator1 __current = __first1;
4675 __first1 = _GLIBCXX_STD_A::find(__first1, __last1, *__first2);
4676 if (__first1 == __last1)
4680 __current = __first1;
4681 if (++__current == __last1)
4684 while (*__current == *__p)
4686 if (++__p == __last2)
4688 if (++__current == __last1)
4717 template<
typename _ForwardIterator1,
typename _ForwardIterator2,
4718 typename _BinaryPredicate>
4720 search(_ForwardIterator1 __first1, _ForwardIterator1 __last1,
4721 _ForwardIterator2 __first2, _ForwardIterator2 __last2,
4722 _BinaryPredicate __predicate)
4725 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator1>)
4726 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator2>)
4727 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4728 typename iterator_traits<_ForwardIterator1>::value_type,
4729 typename iterator_traits<_ForwardIterator2>::value_type>)
4730 __glibcxx_requires_valid_range(__first1, __last1);
4731 __glibcxx_requires_valid_range(__first2, __last2);
4734 if (__first1 == __last1 || __first2 == __last2)
4738 _ForwardIterator2 __p1(__first2);
4739 if (++__p1 == __last2)
4741 while (__first1 != __last1
4742 && !
bool(__predicate(*__first1, *__first2)))
4748 _ForwardIterator2 __p;
4749 _ForwardIterator1 __current = __first1;
4753 while (__first1 != __last1
4754 && !
bool(__predicate(*__first1, *__first2)))
4756 if (__first1 == __last1)
4760 __current = __first1;
4761 if (++__current == __last1)
4764 while (__predicate(*__current, *__p))
4766 if (++__p == __last2)
4768 if (++__current == __last1)
4791 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp>
4793 search_n(_ForwardIterator __first, _ForwardIterator __last,
4794 _Integer __count,
const _Tp& __val)
4797 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4798 __glibcxx_function_requires(_EqualOpConcept<
4799 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4800 __glibcxx_requires_valid_range(__first, __last);
4805 return _GLIBCXX_STD_A::find(__first, __last, __val);
4827 template<
typename _ForwardIterator,
typename _Integer,
typename _Tp,
4828 typename _BinaryPredicate>
4830 search_n(_ForwardIterator __first, _ForwardIterator __last,
4831 _Integer __count,
const _Tp& __val,
4832 _BinaryPredicate __binary_pred)
4835 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
4836 __glibcxx_function_requires(_BinaryPredicateConcept<_BinaryPredicate,
4837 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4838 __glibcxx_requires_valid_range(__first, __last);
4844 while (__first != __last && !
bool(__binary_pred(*__first, __val)))
4848 return std::__search_n(__first, __last, __count, __val, __binary_pred,
4869 template<
typename _InputIterator,
typename _OutputIterator,
4870 typename _UnaryOperation>
4872 transform(_InputIterator __first, _InputIterator __last,
4873 _OutputIterator __result, _UnaryOperation __unary_op)
4876 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
4877 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4879 __typeof__(__unary_op(*__first))>)
4880 __glibcxx_requires_valid_range(__first, __last);
4882 for (; __first != __last; ++__first, ++__result)
4883 *__result = __unary_op(*__first);
4905 template<
typename _InputIterator1,
typename _InputIterator2,
4906 typename _OutputIterator,
typename _BinaryOperation>
4908 transform(_InputIterator1 __first1, _InputIterator1 __last1,
4909 _InputIterator2 __first2, _OutputIterator __result,
4910 _BinaryOperation __binary_op)
4913 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
4914 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
4915 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
4917 __typeof__(__binary_op(*__first1,*__first2))>)
4918 __glibcxx_requires_valid_range(__first1, __last1);
4920 for (; __first1 != __last1; ++__first1, ++__first2, ++__result)
4921 *__result = __binary_op(*__first1, *__first2);
4938 template<
typename _ForwardIterator,
typename _Tp>
4940 replace(_ForwardIterator __first, _ForwardIterator __last,
4941 const _Tp& __old_value,
const _Tp& __new_value)
4944 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4946 __glibcxx_function_requires(_EqualOpConcept<
4947 typename iterator_traits<_ForwardIterator>::value_type, _Tp>)
4948 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4949 typename iterator_traits<_ForwardIterator>::value_type>)
4950 __glibcxx_requires_valid_range(__first, __last);
4952 for (; __first != __last; ++__first)
4953 if (*__first == __old_value)
4954 *__first = __new_value;
4970 template<
typename _ForwardIterator,
typename _Predicate,
typename _Tp>
4972 replace_if(_ForwardIterator __first, _ForwardIterator __last,
4973 _Predicate __pred,
const _Tp& __new_value)
4976 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
4978 __glibcxx_function_requires(_ConvertibleConcept<_Tp,
4979 typename iterator_traits<_ForwardIterator>::value_type>)
4980 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
4981 typename iterator_traits<_ForwardIterator>::value_type>)
4982 __glibcxx_requires_valid_range(__first, __last);
4984 for (; __first != __last; ++__first)
4985 if (__pred(*__first))
4986 *__first = __new_value;
5002 template<
typename _ForwardIterator,
typename _Generator>
5004 generate(_ForwardIterator __first, _ForwardIterator __last,
5008 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
5009 __glibcxx_function_requires(_GeneratorConcept<_Generator,
5010 typename iterator_traits<_ForwardIterator>::value_type>)
5011 __glibcxx_requires_valid_range(__first, __last);
5013 for (; __first != __last; ++__first)
5033 template<
typename _OutputIterator,
typename _Size,
typename _Generator>
5035 generate_n(_OutputIterator __first, _Size __n, _Generator __gen)
5038 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5040 __typeof__(__gen())>)
5042 for (__decltype(__n + 0) __niter = __n;
5043 __niter > 0; --__niter, ++__first)
5070 template<
typename _InputIterator,
typename _OutputIterator>
5071 inline _OutputIterator
5072 unique_copy(_InputIterator __first, _InputIterator __last,
5073 _OutputIterator __result)
5076 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5077 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5078 typename iterator_traits<_InputIterator>::value_type>)
5079 __glibcxx_function_requires(_EqualityComparableConcept<
5080 typename iterator_traits<_InputIterator>::value_type>)
5081 __glibcxx_requires_valid_range(__first, __last);
5083 if (__first == __last)
5109 template<
typename _InputIterator,
typename _OutputIterator,
5110 typename _BinaryPredicate>
5111 inline _OutputIterator
5112 unique_copy(_InputIterator __first, _InputIterator __last,
5113 _OutputIterator __result,
5114 _BinaryPredicate __binary_pred)
5117 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
5118 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5119 typename iterator_traits<_InputIterator>::value_type>)
5120 __glibcxx_requires_valid_range(__first, __last);
5122 if (__first == __last)
5141 template<
typename _RandomAccessIterator>
5143 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
5146 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5147 _RandomAccessIterator>)
5148 __glibcxx_requires_valid_range(__first, __last);
5150 if (__first != __last)
5151 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5152 std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
5169 template<
typename _RandomAccessIterator,
typename _RandomNumberGenerator>
5171 random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
5172 #ifdef __GXX_EXPERIMENTAL_CXX0X__
5173 _RandomNumberGenerator&& __rand)
5175 _RandomNumberGenerator& __rand)
5179 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5180 _RandomAccessIterator>)
5181 __glibcxx_requires_valid_range(__first, __last);
5183 if (__first == __last)
5185 for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
5205 template<
typename _ForwardIterator,
typename _Predicate>
5206 inline _ForwardIterator
5207 partition(_ForwardIterator __first, _ForwardIterator __last,
5211 __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
5213 __glibcxx_function_requires(_UnaryPredicateConcept<_Predicate,
5214 typename iterator_traits<_ForwardIterator>::value_type>)
5215 __glibcxx_requires_valid_range(__first, __last);
5239 template<
typename _RandomAccessIterator>
5241 partial_sort(_RandomAccessIterator __first,
5242 _RandomAccessIterator __middle,
5243 _RandomAccessIterator __last)
5245 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5249 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5250 _RandomAccessIterator>)
5251 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5252 __glibcxx_requires_valid_range(__first, __middle);
5253 __glibcxx_requires_valid_range(__middle, __last);
5278 template<
typename _RandomAccessIterator,
typename _Compare>
5280 partial_sort(_RandomAccessIterator __first,
5281 _RandomAccessIterator __middle,
5282 _RandomAccessIterator __last,
5285 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5289 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5290 _RandomAccessIterator>)
5291 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5292 _ValueType, _ValueType>)
5293 __glibcxx_requires_valid_range(__first, __middle);
5294 __glibcxx_requires_valid_range(__middle, __last);
5316 template<
typename _RandomAccessIterator>
5318 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5319 _RandomAccessIterator __last)
5321 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5325 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5326 _RandomAccessIterator>)
5327 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5328 __glibcxx_requires_valid_range(__first, __nth);
5329 __glibcxx_requires_valid_range(__nth, __last);
5331 if (__first == __last || __nth == __last)
5334 std::__introselect(__first, __nth, __last,
5355 template<
typename _RandomAccessIterator,
typename _Compare>
5357 nth_element(_RandomAccessIterator __first, _RandomAccessIterator __nth,
5358 _RandomAccessIterator __last, _Compare __comp)
5360 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5364 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5365 _RandomAccessIterator>)
5366 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5367 _ValueType, _ValueType>)
5368 __glibcxx_requires_valid_range(__first, __nth);
5369 __glibcxx_requires_valid_range(__nth, __last);
5371 if (__first == __last || __nth == __last)
5374 std::__introselect(__first, __nth, __last,
5375 std::__lg(__last - __first) * 2, __comp);
5393 template<
typename _RandomAccessIterator>
5395 sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5397 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5401 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5402 _RandomAccessIterator>)
5403 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5404 __glibcxx_requires_valid_range(__first, __last);
5406 if (__first != __last)
5429 template<
typename _RandomAccessIterator,
typename _Compare>
5431 sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5434 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5438 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5439 _RandomAccessIterator>)
5440 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare, _ValueType,
5442 __glibcxx_requires_valid_range(__first, __last);
5444 if (__first != __last)
5447 std::__lg(__last - __first) * 2, __comp);
5470 template<
typename _InputIterator1,
typename _InputIterator2,
5471 typename _OutputIterator>
5473 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5474 _InputIterator2 __first2, _InputIterator2 __last2,
5475 _OutputIterator __result)
5477 typedef typename iterator_traits<_InputIterator1>::value_type
5479 typedef typename iterator_traits<_InputIterator2>::value_type
5483 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5484 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5485 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5487 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5489 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5490 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5491 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5493 while (__first1 != __last1 && __first2 != __last2)
5495 if (*__first2 < *__first1)
5497 *__result = *__first2;
5502 *__result = *__first1;
5507 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5533 template<
typename _InputIterator1,
typename _InputIterator2,
5534 typename _OutputIterator,
typename _Compare>
5536 merge(_InputIterator1 __first1, _InputIterator1 __last1,
5537 _InputIterator2 __first2, _InputIterator2 __last2,
5538 _OutputIterator __result, _Compare __comp)
5540 typedef typename iterator_traits<_InputIterator1>::value_type
5542 typedef typename iterator_traits<_InputIterator2>::value_type
5546 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5547 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5548 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5550 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5552 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5553 _ValueType2, _ValueType1>)
5554 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5555 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5557 while (__first1 != __last1 && __first2 != __last2)
5559 if (__comp(*__first2, *__first1))
5561 *__result = *__first2;
5566 *__result = *__first1;
5571 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5593 template<
typename _RandomAccessIterator>
5595 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last)
5597 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5599 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5603 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5604 _RandomAccessIterator>)
5605 __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)
5606 __glibcxx_requires_valid_range(__first, __last);
5610 if (__buf.
begin() == 0)
5613 std::__stable_sort_adaptive(__first, __last, __buf.
begin(),
5614 _DistanceType(__buf.
size()));
5635 template<
typename _RandomAccessIterator,
typename _Compare>
5637 stable_sort(_RandomAccessIterator __first, _RandomAccessIterator __last,
5640 typedef typename iterator_traits<_RandomAccessIterator>::value_type
5642 typedef typename iterator_traits<_RandomAccessIterator>::difference_type
5646 __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
5647 _RandomAccessIterator>)
5648 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5651 __glibcxx_requires_valid_range(__first, __last);
5655 if (__buf.
begin() == 0)
5658 std::__stable_sort_adaptive(__first, __last, __buf.
begin(),
5659 _DistanceType(__buf.
size()), __comp);
5681 template<
typename _InputIterator1,
typename _InputIterator2,
5682 typename _OutputIterator>
5684 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5685 _InputIterator2 __first2, _InputIterator2 __last2,
5686 _OutputIterator __result)
5688 typedef typename iterator_traits<_InputIterator1>::value_type
5690 typedef typename iterator_traits<_InputIterator2>::value_type
5694 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5695 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5696 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5698 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5700 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5701 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5702 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5703 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5705 while (__first1 != __last1 && __first2 != __last2)
5707 if (*__first1 < *__first2)
5709 *__result = *__first1;
5712 else if (*__first2 < *__first1)
5714 *__result = *__first2;
5719 *__result = *__first1;
5725 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5748 template<
typename _InputIterator1,
typename _InputIterator2,
5749 typename _OutputIterator,
typename _Compare>
5751 set_union(_InputIterator1 __first1, _InputIterator1 __last1,
5752 _InputIterator2 __first2, _InputIterator2 __last2,
5753 _OutputIterator __result, _Compare __comp)
5755 typedef typename iterator_traits<_InputIterator1>::value_type
5757 typedef typename iterator_traits<_InputIterator2>::value_type
5761 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5762 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5763 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5765 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5767 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5768 _ValueType1, _ValueType2>)
5769 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5770 _ValueType2, _ValueType1>)
5771 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5772 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5774 while (__first1 != __last1 && __first2 != __last2)
5776 if (__comp(*__first1, *__first2))
5778 *__result = *__first1;
5781 else if (__comp(*__first2, *__first1))
5783 *__result = *__first2;
5788 *__result = *__first1;
5794 return std::copy(__first2, __last2, std::copy(__first1, __last1,
5815 template<
typename _InputIterator1,
typename _InputIterator2,
5816 typename _OutputIterator>
5818 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5819 _InputIterator2 __first2, _InputIterator2 __last2,
5820 _OutputIterator __result)
5822 typedef typename iterator_traits<_InputIterator1>::value_type
5824 typedef typename iterator_traits<_InputIterator2>::value_type
5828 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5829 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5830 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5832 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5833 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5834 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5835 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5837 while (__first1 != __last1 && __first2 != __last2)
5838 if (*__first1 < *__first2)
5840 else if (*__first2 < *__first1)
5844 *__result = *__first1;
5872 template<
typename _InputIterator1,
typename _InputIterator2,
5873 typename _OutputIterator,
typename _Compare>
5875 set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
5876 _InputIterator2 __first2, _InputIterator2 __last2,
5877 _OutputIterator __result, _Compare __comp)
5879 typedef typename iterator_traits<_InputIterator1>::value_type
5881 typedef typename iterator_traits<_InputIterator2>::value_type
5885 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5886 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5887 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5889 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5890 _ValueType1, _ValueType2>)
5891 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
5892 _ValueType2, _ValueType1>)
5893 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
5894 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
5896 while (__first1 != __last1 && __first2 != __last2)
5897 if (__comp(*__first1, *__first2))
5899 else if (__comp(*__first2, *__first1))
5903 *__result = *__first1;
5930 template<
typename _InputIterator1,
typename _InputIterator2,
5931 typename _OutputIterator>
5933 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5934 _InputIterator2 __first2, _InputIterator2 __last2,
5935 _OutputIterator __result)
5937 typedef typename iterator_traits<_InputIterator1>::value_type
5939 typedef typename iterator_traits<_InputIterator2>::value_type
5943 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
5944 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
5945 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
5947 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
5948 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
5949 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
5950 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
5952 while (__first1 != __last1 && __first2 != __last2)
5953 if (*__first1 < *__first2)
5955 *__result = *__first1;
5959 else if (*__first2 < *__first1)
5966 return std::copy(__first1, __last1, __result);
5991 template<
typename _InputIterator1,
typename _InputIterator2,
5992 typename _OutputIterator,
typename _Compare>
5994 set_difference(_InputIterator1 __first1, _InputIterator1 __last1,
5995 _InputIterator2 __first2, _InputIterator2 __last2,
5996 _OutputIterator __result, _Compare __comp)
5998 typedef typename iterator_traits<_InputIterator1>::value_type
6000 typedef typename iterator_traits<_InputIterator2>::value_type
6004 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6005 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6006 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6008 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6009 _ValueType1, _ValueType2>)
6010 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6011 _ValueType2, _ValueType1>)
6012 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6013 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6015 while (__first1 != __last1 && __first2 != __last2)
6016 if (__comp(*__first1, *__first2))
6018 *__result = *__first1;
6022 else if (__comp(*__first2, *__first1))
6029 return std::copy(__first1, __last1, __result);
6049 template<
typename _InputIterator1,
typename _InputIterator2,
6050 typename _OutputIterator>
6052 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6053 _InputIterator2 __first2, _InputIterator2 __last2,
6054 _OutputIterator __result)
6056 typedef typename iterator_traits<_InputIterator1>::value_type
6058 typedef typename iterator_traits<_InputIterator2>::value_type
6062 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6063 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6064 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6066 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6068 __glibcxx_function_requires(_LessThanOpConcept<_ValueType1, _ValueType2>)
6069 __glibcxx_function_requires(_LessThanOpConcept<_ValueType2, _ValueType1>)
6070 __glibcxx_requires_sorted_set(__first1, __last1, __first2);
6071 __glibcxx_requires_sorted_set(__first2, __last2, __first1);
6073 while (__first1 != __last1 && __first2 != __last2)
6074 if (*__first1 < *__first2)
6076 *__result = *__first1;
6080 else if (*__first2 < *__first1)
6082 *__result = *__first2;
6091 return std::copy(__first2, __last2, std::copy(__first1,
6092 __last1, __result));
6115 template<
typename _InputIterator1,
typename _InputIterator2,
6116 typename _OutputIterator,
typename _Compare>
6118 set_symmetric_difference(_InputIterator1 __first1, _InputIterator1 __last1,
6119 _InputIterator2 __first2, _InputIterator2 __last2,
6120 _OutputIterator __result,
6123 typedef typename iterator_traits<_InputIterator1>::value_type
6125 typedef typename iterator_traits<_InputIterator2>::value_type
6129 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
6130 __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
6131 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6133 __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
6135 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6136 _ValueType1, _ValueType2>)
6137 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6138 _ValueType2, _ValueType1>)
6139 __glibcxx_requires_sorted_set_pred(__first1, __last1, __first2, __comp);
6140 __glibcxx_requires_sorted_set_pred(__first2, __last2, __first1, __comp);
6142 while (__first1 != __last1 && __first2 != __last2)
6143 if (__comp(*__first1, *__first2))
6145 *__result = *__first1;
6149 else if (__comp(*__first2, *__first1))
6151 *__result = *__first2;
6160 return std::copy(__first2, __last2,
6161 std::copy(__first1, __last1, __result));
6172 template<
typename _ForwardIterator>
6174 min_element(_ForwardIterator __first, _ForwardIterator __last)
6177 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6178 __glibcxx_function_requires(_LessThanComparableConcept<
6179 typename iterator_traits<_ForwardIterator>::value_type>)
6180 __glibcxx_requires_valid_range(__first, __last);
6182 if (__first == __last)
6184 _ForwardIterator __result = __first;
6185 while (++__first != __last)
6186 if (*__first < *__result)
6200 template<
typename _ForwardIterator,
typename _Compare>
6202 min_element(_ForwardIterator __first, _ForwardIterator __last,
6206 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6207 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6208 typename iterator_traits<_ForwardIterator>::value_type,
6209 typename iterator_traits<_ForwardIterator>::value_type>)
6210 __glibcxx_requires_valid_range(__first, __last);
6212 if (__first == __last)
6214 _ForwardIterator __result = __first;
6215 while (++__first != __last)
6216 if (__comp(*__first, *__result))
6228 template<
typename _ForwardIterator>
6230 max_element(_ForwardIterator __first, _ForwardIterator __last)
6233 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6234 __glibcxx_function_requires(_LessThanComparableConcept<
6235 typename iterator_traits<_ForwardIterator>::value_type>)
6236 __glibcxx_requires_valid_range(__first, __last);
6238 if (__first == __last)
6240 _ForwardIterator __result = __first;
6241 while (++__first != __last)
6242 if (*__result < *__first)
6256 template<
typename _ForwardIterator,
typename _Compare>
6258 max_element(_ForwardIterator __first, _ForwardIterator __last,
6262 __glibcxx_function_requires(_ForwardIteratorConcept<_ForwardIterator>)
6263 __glibcxx_function_requires(_BinaryPredicateConcept<_Compare,
6264 typename iterator_traits<_ForwardIterator>::value_type,
6265 typename iterator_traits<_ForwardIterator>::value_type>)
6266 __glibcxx_requires_valid_range(__first, __last);
6268 if (__first == __last)
return __first;
6269 _ForwardIterator __result = __first;
6270 while (++__first != __last)
6271 if (__comp(*__result, *__first))
6276 _GLIBCXX_END_NAMESPACE_ALGO